Skip to main content

Full text of "Optimal control of oversaturated signal systems : some theoretical considerations"

See other formats


OPTIMAL CONTROL OF OVERSATURATED SIGNAL SYSTEMS 
SOME THEORETICAL CONSIDERATIONS 



By 



PANAYOTIS GEORGE MICHALOPOULOS 



A DISSERTATION PRESENTED TO THE GRADUATE COUNCIL OF 

THE UNIVERSITY OF FLORIDA 
IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE 
DECREE OF DOCTOR OF PHILOSOPHY 



UNIVERSITY OF FLORIDA" 



1975 



ACKNOWLEDGMENTS 

I would like to thank my advisor, Dr. J. A. Wattleworth, 
for his useful suggestions, encouragement, and support, I 
also thank Professor K. G. Courage for his help and interest 
shown during the preparation of this dissertation. I would 
like to express my gratitude to Dr. George Stephanopoulos for 
his advice and counsel in the areas of this dissertation that 
are outside of the field of transportation engineering. 



Recognition is also due to Dr. J. H. Schaub 



ur , 



L. 



and 



R. S. Leavenworth for their encouragement during 



preparation of this work. Last, but certainly no1 



1 a n c 



appreciation is expressed to my colleagues B. Fan an an ou and 
Jim Hurley for their interest and moral support in this 
en de a vo r an d for th e i r us e £u 1 s u g g e s t i on s . 



1 1 



TABLE OF CONTENTS 



2 LITERATURE REVIEW 



4 


3. 


4 


4. 


4 


• > - 


4 


6 ., 



Page 



ii 



ACKNOWLEDGMENTS .... 

ABSTRACT • , v 

CHAPTER 

1 INTRODUCTION ......... 1 



i 



1.1. Statement of the Problem 

1.2. Scope of the Study . , 3 

1.3. Organization 4 



2.1. Preface .......... 6 

2.2. The Existing Theories ......... 7 

INTRODUCTION TO OPTIMAL CONTROL THEORY ..... 21 

3.1. Preface ................ 21 

3.2. Optimal Control System Design ..... 23 

3.3. The Concepts of State and 

State Variables 26 

3.4. The Performance Index ......... 29 

3.5. Pontryagin's Maximum Principle 3 



-? 



SINGLE OVERSATURATED INTERSECTION 37 

4.1. Formulation of the Unconstrained 

Problem . . . 37 

4.2. Optimal Control with State 

Variable Constraints 52 

Solution to the Unconstrained 

P r ob 1 e m ................ 63 

Solution to the Constrained Problem . . 66 

Some Computational Aspects . . . . . . . 75 

The Optimum Cycle Length .... 76 

CONTROL WITH BUS PRIORITIES ....... 79 

Statement of the Problem ........ 79 

Development of the Control Strategy . . 81 



1 1 1 



TABLE OF CONTENTS - continued 



90 



Page 

CHAPTER 

6 SYSTEMS OF OVERS ATURATED INTERSECTIONS 9 

6,1. 
6.2. 
6.. 3. 
6.4. Solution to the Constrained Problem 

7 EXTENSIONS OF THE THEORY . . 



Formulation of the Unconstrained 

Problem .....' 

Optimal Control with State 

Variable Constraints .......... 100 

Solution to the Unconstrained 

Problem .10 5 

. . 108 



7.1. Single Oversaturated Intersection 

7.2. Systems of Intersections .... 

CONCLUSIONS AND RECOMMENDATIONS . . . . , 



113 

113 
115 



APPENDIX 



k APPLICATIONS OF THE THEORY . 



A. 


1. 


A. 


2 . 


A. 


3, 


A. 


4. 


A. 


5. 


A. 


6 . 



12 2 

12 2 

126 



Introduction ....... 

The Unconstrained Problem ...... 

The Optimal Cycle Length ........ 130 

The Fixed Final Time Problem . . . . . . 133 

The Constrained Problem ........ 134 



Sens iti vi ty An aly s i s 

LIS1' OF REFERENCES 

BIOGRAPHICAL SKETCH ........ 



. 141 
. 144 



i v 



Abstract of Dissertation Presented to the Graduate Council 
of the University of Florida In Partial Fulfillment of the 
Requirements for the Degree of Doctor of Philosophy 



OPTIMAL CONTROL OF OVERSATURATED SIGNAL SYSTEMS: 
SOME THEORETICAL CONSIDERATIONS 



by 

Panayotis George Michalopoulos 

December, 1975 

Chairman: J. A. Wattleworth 

Major Department: Civil Engineering 



The timing of traffic signals is one of the major prob- 
lems in traffic engineering practice. While several theories 
have been developed for the control of undersaturated inter- 
sections, little theoretical work has been performed for 
oversaturated conditions. The objective of this research is 
to develop the theory for the optimal signal settings of over 
saturated intersections. The mathematical analysis Is based 
state-of-the-art of optimal control theory. The folio-. 






ing problems are treated assuming nonlinear time varying 
demands: (1) minimization of total delay of isolated over- 
saturated intersections, (2) minimization of total delay sub 
ject to queue length constraints, (3) optimum cycle length 
determination, (4) bus priorities at oversaturated intersec- 
tions, (S) minimization of the total delay of two consecutiv; 



oversaturated Intersections with and without 



npnp a 



u ut 



ntJth 



constraints, including the effects of turning volumes and 



travel time between th 



e intersections, ana (.5 J optimal 



control of a system of more than two overs aturated Inter- 
sections In succession. 

Numerical examples are presented to, demonstrate the 
effectiveness of the theory under different formulations. 



VI 



CHAPTER 1 
INTRODUCTION 

i . 1 . St atement of the Problem 

The problems associated with vehicular traffic moving 
through a city network of streets are numerous. The intro- 
duction of freeways has changed the patterns of traffic and 
has somewhat relieved congestion on surface streets; but the 
signalized intersection continues to be a major problem. 

The traffic demand at signalized intersections varies 
throughout the day and congestion frequently occurs during 
the morning and afternoon peak periods due to the large 
numbers of people driving to or from work. 

During the periods of congestion, the demand exceeds the 
capacity of the intersection, causing queuing conditions to 
develop. These conditions continue until, at some point in 
time, demand has decreased to a level below capacity such 
that the queues are dissolved. When these conditions develop 
the intersection is called overs aturated or congested. 

Congestion at signalized intersections can be prevented 
either by building new transportation facilities or by 
increasing the capacity of the intersection. However, con- 
struction of new facilities is not always feasible in urban 
areas, where congestion problems are most severe, nor does it 



necessarily result in complete elimination of the problem. 
The intersection capacity can be increased by proper chan- 
nelization, peak period parking restrictions, prohibition of 
certain movements during the peak hours, installation of 
traffic control devices, and ether conventional traffic con- 
trol measures. Nonetheless, these measures have certain limi- 
tations, and congestion at most signalized intersections dur- 
ing the peak periods is unavoidable. The duration of the 
congested period is a function of the demand at the inter- 
section as 'well as its capacity. 

Congestion can further be relieved by proper control of 
the traffic signals. The timing of traffic signals is one 
of the major problems in traffic engineering practice. While 
several theories have been developed (and applied success- 
fully) for the control of undersaturated intersections, little 
theoretical work has been performed for overs aturated condi- 
tions. At this time, only one theory has been developed for 
pre timed (open loop) control of overs aturated traffic signals. 
However, due to its limitations and some oversimplified assump- 
tions, this theory cannot be applied in practice. For real- 
time (feedback) control, few theories have been developed; 
but it should be noted that none have been applied in a real 
system, partly because of the extensive instrumentation and 
computational requirements and partly because traffic engi- 
neers tend to avoid extensive departure from conventional 
methods. Furthermore, some theories are based on assumptions 
which are unrealistic. For those reasons, the methods 



presently used by traffic engineers are dependent on prac- 
tical considerations. There is clearly a need for a realis- 
tic theory to solve the problem of control of overs at urate d 
inte rsections . 



1.2. Scope of the Study 

Development of a theory for optimal signal control of 
overs aturated intersections is the objective of this disser- 
tation. The mathematical analysis is based on the current 
state of development of optimal control theory. The problems 
that have been studied are formulated and solved as optimal 
control problems. Unlike previous theories, the assumptions 
and proposed solutions reflect real-world situations so that 
the results are directly applicable in practice. The follow- 
ing problems have been studied. 

1 . Optimal control of an i sol ated oversaturate d inter - 
section with, lower bound constraints on the queue lengths . 

The only objective of the control is minimization of the total 
de 1 ay . 

2 . O ptimal control with upper and lower bounds placed 
on the q ueue l e ngth s. Minimization of the total delay is the 
objective of the control, but the queues are not allowed to 
exceed a predetermined upper limit (to prevent blocking up- 
stream intersections). in this case, the resulting delay is 
higher and the control becomes complex, 

3. Bus pr ioritie s at o vers aturated i ntersections . Mini- 
mization of the total passenger delay is the objective of this 
control. . 



4 



Optimal control of a system of two overs aturated 



intersections in success ion. This problem is not a simple 
extension of- the problems listed previously. The number of 
control variables, turning volumes, and time delays of the 
control that are introduced enlarge the problem considerably. 
That is, the control action at the downstream intersection at 
time t is a function of the control action taken at the up- 
stream intersection at time t-d where d is the travel time 
between the two intersections, Minimization of total "system" 
delay is the objective of the control with lower bounds and 
upper bounds on queue lengths. 

5 - Optimal control of a system of more than two over- 
s atu rate d in te rsection s. The theory of item 4 is extended to 
include more than two oversaturated intersections in succes- 
sion. 

Num.eric.al examples are given to demonstrate the applica- 
bility and the effectiveness of the theory under different 
formulations. It should be emphasized that in the development 
of the theory, demands are assumed to be time varying as in 
reality. Furthermore, no particular assumptions are made 
concerning the patterns of the demands. The theory is also 
applicable for initial and final states other than zero and 
for cases in which the control period is prescribed. 

1 . 3 . ^Kf 11 !! z at ion 

The existing theories are discussed in Chapter 2. Chap- 
ter 3 introduces the fundamental principles of optimal control 



theory which constitute the basis of the mathematical analyse 
that are performed in subsequent chapters. The solutions of 
the problems associated with a single intersection are devel- 
oped in Chapter 4. In Chapter 5, a control scheme for bus 
priorities is developed. Chapter 6 includes the solution of 
the problems associated with a system, of two overs aturated 
intersections ; and the theory is extended for more than two 
intersections in Chapter 7. A summary of major findings and 
suggestions for future research are given in Chapter 8. 
Finally, several numerical examples are given in Appendix A. 



CHAPTER 2 
LITERATURE REVIEW 



2.1. Preface 



Although the problem of optimizing the operation of over- 
saturated intersections is not new, little theoretical work 
for its solution has been performed. For pretimed traffic 
control the only theory thus far developed is that of Gazis 
and Potts, whereas for real-time control the most widely 
known works are those of Miller/' Ross et al . , ' and Longley,' 
The methods presently used by most traffic analysts are empiri 
cal in form since the theories that have been developed for 

unders aturated intersections are not valid for overs aturated 

1 

ones, and the theory of Gazis and Potts" contains certain 

unrealistic assumptions that make its use- questionable for 
real-world situations. In addition, the algorithms developed 
by Ross e_t al . , Longley, and Lee are semi -empirical, and 
as such they do not constitute true optimal control policies. 
Therefore, testing of these models requires use of simulation 
techniques. It should be emphasized that up to now, none of 
the theories developed has been applied in a real system. 

What is needed, then, is a theoretical formulation that 
does not rely on simulation, but actually shows why and how 
to optimally control overs aturated signalized intersections. 



Before describing a realistic optimal control procedure, a 
discussion of existing theories is in order. 

2,2. The Existing Theories 



Gazis and Potts" consider an intersection serving two 
competing demands associated with time varying arrival rates 
q-j (t) and q_ 2 (t) . A sufficient condition for overs at urat ion 
is given by 

q l /s l + q 2 /s 2 > 1 " ( L/c ^ (2.2.1) 

where q 1? q ? = the arrival rates (vehicles per unit of time) 

s ]_j s 2 = the saturation flows (vehicles per unit of time) 
c = the cycle length (seconds) 
L = the total lost time per cycle (seconds). 
Assuming that at the beginning of ove rs aturation period 
there are no queues on either of the two approaches, the cumu- 
lative demand functions are given by 

T i 
Q-i (t) = J q^ (t)dt i = 1,2 (2.2.2) 

o 

where the time origin (zero) is the onset of overs aturation 

and T is the final time at which the queues are dissipated. 

The LLiaewj.se variation of cumulative service volume for a 

given approach is characterized by a saw-toothed pattern such 

as that shown in Figure 2.1. Assuming that this saw- toothed 

pattern, caused by the intermittent serving of traffic by the 

light, caa be represented by a straight line, the cumulative 

service functions G, (t) are given by 




Figure 2 . 1 



G.(t) - / Y i (t)dt 

o 



1,2 



(2.2.3) 



where y- is the service rate of approach i. 
is defined as 



ihe service rate 



Y x (t) 



gi(t) 



i = 1,2 



(2.2.4) 



where g- is the effective green time that is given to 
approach i. 



If the saturation flows s, and s_ of the conflicting 
streams arc equal, the aggregate delays are minimized when 
both queues are dissolved simultaneously, and this is accom- 
plished by a single setting of the light, so that the follow 
ing relationships are satisfied: 



QiCT) - -^i- =0 i * 1,2 ' (2.2.5) 

S 1 + g 2 + L a c , (2.2.6) 

where T is the final time at which the queues are dissolved. 

In the more general case, however, where saturation 
flows are unequal, i.e., s, > s-, the 'single setting strategy 
is not the only one that dissolves both queues simultaneously, 
nor does it constitute the control that minimizes the aggre- 
gate delay. In this case, the aggregate delay can be reduced 
by trading off some delay for the major stream, i.e., the one 
associated with the maximum saturation flow (s,) for smaller 
amounts of delay of the other stream. This is accomplished 
by setting upper and lower bounds on the green times for each 
phase. The optimal strategy which simultaneously dissolves 
both queues at the earliest possible time corresponds in 
general to a two-stage operation. During the first stage 
the direction associated with the highest saturation flow 
receives maximum green time (the second approach consequently 
receives minimum green). In the second stage the service 
rates are reversed, i.e., minimum green time is given to the 
first direction and maximum to the second. The switching from 
one extreme of the control variable (in this case green time) 
to another is generally referred to as "bang-bang control" In 
control theory. 

Under the assumptions that no constraints are placed on 
the queue lengths, that the input curves are explicit func- 
tions o £ time j and considering two streams only, the 



10 



switchover point and the earliest end of ova rs aturation period 
can be found. By approximating the input curves fay linear 
functions of time of the form 

Qi(t) = A. + B.t (2.2.7) 

the switchover point and the final time are determined by the 
relationships 

A, s +A 9 s 

T.1 L L JL 
(2.2.8) 

(B l S 2 + B 2 S r + S l s 2 (1 "c i) 



t = [(c/s.) -Q. (T)-g . T](g -g . ) _1 f 2 . 2 9^ 



- -X 



here g mnv ,g_,z_, are the upper and lower bounds of the effec- 
tive green time of the first approach, and T is the switchover 
time. The above formulas allow negative queue lengths, and 
must therefore be used with caution. 

Gazis and Potts also made an unsuccessful attempt to 
find the optimum cycle length, assuming linear demand curves 
as before. Even with the oversimplified demand function, the 
complexity of the problem was such that to obtain a solution, 
B., and B ? had to be assumed equal to zero, i.e., no input 



it. 



a 1 1 e r time ze r o . 

7 

Green' also attempted to find the optimum cycle length 
assuming linear demand curves and also that 



A i = A 2 ;= A (2.2 .10) 

B} ^ B, - B and (2.2.11) 

S , - S „ ~ S (? 



12) 



11 

These assumptions are better than the previous ones but they 
are again unrealistic. Making the above assumptions and con- 
sidering two approaches, Green derived the following expres- 
sion for optimum cycle length 

sL 2 r ?R i /-, 

C opt = ^TB + i^TI" [BL (s-f-3 + ALCS-2B)] 1 / 2 (2.2.13J 

q 

Gazis also considered a pair of intersections of three 
one-way streets such as shown in Figure 2.2 and assumed that 
the transit time and queueing storage between intersections 
are negligible and that the intersections become oversaturated 
at approximately the same time. These assumptions, of course, 
oversimplify the problem because the two intersections are 
treated as one and thus the problem is the same as that for 
the single intersection. With these rather unrealistic 
assumptions, Gazis gives a similar policy improvement scheme 
as that for the single intersection. Unlike the single inter- 
section case, the problem is not formulated as an optimal con- 
trol problem. As will be shown in Chapter 6, the solution of ■ 
this problem is not an easy one since there are two control 
variables, and time delay of the control is introduced. 

It should be emphasized that, although the work of Gazis 
is a major breakthrough in this area, it has some inherent 
disadvantages which make it difficult to apply direct!' 
real-world situation. The major disadvantage of the theory 
is that no constraints are placed on the queue lengths. Wh< 
an intersection is oversaturated the problem is not only to 
minimize the aggregate delays of the conflicting strrw 



:o a 



I 



4 1 



«^1 




Figure 2 . 2 



q, 



12 



but also to restrict the queues so that they do not block 
upstream intersections , 

A second disadvantage is that in a real-world situation 
the cumulative demand curves are nonlinear. For the pair of 
intersections the basic assumptions are clearly unrealistic 
and thus the problem is not actually solved. Similarly, the 
assumptions for computation of the optimal cycle length are 
unrealistic . 

The work of Miller ' and Ross et al_. is discussed next, 
but it is emphasized that this theory as well as the subse- 
quent ones applies for real-time control systems only. Miller 
considers a four-way intersection with heavy traffic on the 
two arms 1 and 2, and assumes that at time t the signal is 
green on approach 1. At this time the controller can make a 
binary decision, i.e., to change the signals Immediately 
(alternative A) , or alter an extension of one unit of time 



15 

(alternative B) . Assuming that an extension of the present 
phase will simply displace all future changes by the same 
amount of time, the differences in delays can be approximated, 
The difference in total delay caused by choosing alternative 
A over alternative B is the sum of the three terms 



+ 5 i .\ ^ + v 
j=i j 

* 1 ± i 



(2.2.14) 

(2.2.15) 
(2.2.16) 



where 6, = the number of extra vehicles which would 
pass through the junction if the current 
phase were extended by one time unit; 

k = the number of cycles required to exhaust 
b o th q ue ue s ; 

r\. = the duration of the j L " red on arm 1; 

£-. = the time lost in acceleration on arm 1; 

S-, = the average saturation flow on arm 1; and 

N, ,N« = the number of vehicles on arms 1 and 2, 

respectively, which will pass through the 
junction before both queues have been 
exhausted. 

A test function T is then defined which is equal to the 

sum of the three terms listed above. If T is positive, the 

extension should be granted. If T is negative, extension is 

not granted. Similar considerations apply for extension of 

the green time for two, three or more extensions before endin* 

the curren t plias e . 



14 



2 ,o 



Miller"'"" did not consider the interactions of adjacent 
intersections, and thus did not include the downstream delays 
in determining an optimum extension strategy. Weinberg et al. 9 
pursued Miller's model further by including downstream delays 
and deriving equations for the prediction of total delay as 
a function of the extension period. Weinberg et al. also 

extended the theory for more than two phases. 

4 
Ross et al. , basing their work on a philosophy similar 

to that of Miller and Weinberg, developed a computer control 
scheme for traffic, responsive control of a critical intersec- 
tion that not only minimizes the total delay of all users of 
the intersection, but also minimizes the total delay accumu- 
lated at downstream intersections. This was accomplished by 
further simplifying Weinberg's model. According to this 
scheme, the cycle length of the critical intersection is 
allowed to vary between a maximum and a minimum value; however, 
the cycle lengths of the adjacent intersections were assumed 
constant. The turning movements were ignored and the effect 
of downstream residual queues upon total delay were assumed 
negligible. The new scheme was compared with that of fixed 
time control by means of simulation and was found beneficial. 

There are certain disadvantages associated with the above 
theories. The first is that when the intersection is over- 
saturated, a single extension of a phase does not simply dis- 
place ail future signal changes by one unit of time as was 
basically assumed by Miller 2,0 and others using the same con- 
cept. This may be approximately true for undersaturated 



15 

conditions for which Miller's model also applies, but for 
overs at ur ate d conditions this assumption is questionable- 
since the queues are not exhausted in the "next cycle" if the 
previous cycle is extended by n • At units of time. 

The other major disadvantage is that in order to apply 
these models, predictions of several variables are necessary. 
These predictions reduce the accuracy "of the estimation of 
the intersection "gain" T. 

Another disadvantage is that the effects of downstream 
residual queues upon total delay are not negligible as was 
assumed by Ross e_t al. , but should be taken into account 
when system delay is considered. 

in addition, no theory was developed for a system of 

overs aturated intersections . 

1 
According to Gazis, 'the above schemes could probably 

be improved by application of the familiar techniques of 
adaptive control suggested by Kwakernaak [11] for a single inter- 
section, namely, predicting for the next five periods and 
applying the best strategy for one period only." None of 
these schemes has been tested as yet in a real system, partly 
because of the relatively extensive instrumentation and com- 
putation requirements, and partly because traffic engineers 
tend to avoid extensive departure from conventional systems. 

Minimization of total delay was the objective of the con- 
trol theories discussed thus far. Attention is now given to 
theories where emphasis is given to queue lengths rather than 
to aggregate delays. 



16 



A control scheme for a two-phase congested intersect! 



on 



employing a "queue balancing" strategy was proposed by Long- 
ley. This strategy seeks to hold a particular linear func- 
tion of the intersection queues to a value of zero by adjust- 
ment of the green time split. This linear function is termed 

p 

the "queue unbalance" (Q.) and may be defined as 



Q i = <*il + ^13 " B i 2 Q i2 B i4Qx4 



(2,2.17) 



where i denotes a particular intersection and j = 1,2,3,4 is 
a particular approach. The queues (Q. .) are measured at the 
end of the appropriate green period, and the B. . terms are 
weighting factors indicating the relative undesir ability of 
the queue on the appropriate arm; the green time split is 
adjusted in the succeeding cycle so as to reduce the queue 
i nib a 1 an ce to zero. 

If the total traffic flow to the junction is high, but 
below saturation level, this strategy will ensure that ail 
queues with nonzero weighting factors will gradually disperse 
and the green times will be proportional to the total traffic 
flows on opposing arms. If the traffic flow exceeds the satu- 
ration level, the queues will inevitably increase, but the 
desired balance will be maintained and the green split will 
again depend upon the traffic flow, This, of course, does 
not necessarily mean that the queues will remain below some 
predetermined upper limits. The control action is achieved 
by varying the green time for arms 1-3 which move simultane- 
ously in accordance with the relationship 



17 
n-2 



g,Ci) - A. Q.Cn-lj + B j _ £ Qf (in) (2. 2. IS) 

ni=0 



where g i (n) is the value of green time for arms 1-3 on inter- 
section i in excess of its equal split value during the n th 
traffic light cycle. The parameters A. and B. are called the 
proportional and integral controller gains, respectively, and 
their values must be selected (empirically) with care to 
ensure a satisfactory behavior of the signal. 

According to Longley, the proportional controller simply 
increases the green time for arms 1-3 whenever the queue 
balance is positive and vice versa. The integral controller 
seeks to ensure that no steady-state queue unbalance exists 
when the total traffic flows on opposing arms are themselves 
unb alanced. 

The difficulty here lies in the selection of the param- 
eters A 1 and B i which must be determined empirically and also 
in the definition of the queue which, due to the various com- 
putational difficulties, is relaxed to include all the traffic 
within a certain distance of the intersection. In addition, 
the queues are not measured constantly but only after the 
end of the green period. This makes the method inflexible, 
considering the fact that it is designed for real-time con- 
trol. Thus, the decision is made for the next cycle rather 
than for the present cycle as it is done with the real-time 
control methods mentioned previously. 

For the system of intersections, Longley 5 considers a 
perfectly symmetric network with equal input flows on all 



18 

arms, and an Input flow rate exactly balanced by an output, 
flow rate on each arm. In addition, he assumed that equal 
queues --at the end of the appropriate green pe riods - -exist 
on ail arms and the queue unbalance is therefore zero. Using 
these obviously unrealistic assumptions, Longley derives the 
f o 1 1 ow ing f o rmul as : 

B B n " 2 r 

QiCn) = -Q i (n-1) - I Q?(X) + cA (2.2.19) 

m=0 
g . = |_ [Q^Cn-1) + I Z Q*(m)J (2.2.20) 

If g- L > g m # gj_ is recomputed by 

g i = '" S i Cg i^ g m (2.2.21) 

where g is the modulus of the maximum permitted green time 
deviation, c is the cycle length (which is assumed constant), 
A is the difference of the input flows between the two pairs 
of arms, and S. Is given by 



c 



i = S il + B I2 S i2 + B i3 S i3 + B i4 S i4 (2.2.22) 



Again, turning volumes are Ignored as with the single inter- 
se ction . 

T 6 

Lee ?:f.. f~±.« also considered queues rather than delays 
as the objective of the control and developed another semi- 
empirical strategy called "Queue Actuated Signal Control." 
This is a control policy where an approach receives green 
automatically when the queue on that approach becomes equal 
to or greater than some predetermined length, regardless of 



19 

the conditions on the conflicting approaches. The policy- 
assumes that no two conflicting approaches reach the upper 
bound specified for them simultaneously. 

The assumption that the queue lengths will not reach 
their upper bound simultaneously- implies light overs aturation , 
but even in this case this possibility should not be excluded. 
This situation will certainly arise in case of heavy over- 
saturation and it is therefore necessary to establish a maxi- 
mum and minimum cycle length, as well as a maximum green time. 
This control policy is based on the concept that when queues 
on approach A grow to a critical length, approach A should 
get a green phase and keep it until the same condition arises 
on approach B. The placement of the detectors required for 

this type of operation must be determined empirically. Pig- 

1? 
nataro et al. point out that this control policy disrupts 

signal coordination when the intersection is located in the 

midst of an area of coordinated signals. In addition, for 

heavy overs aturation the cycle length becomes short and this 

general!}- increases total delays. 

Making the assumption that the arrival rates are Poisson 

and assuming an intersection of two one-way streets, Lee 

. , 6 . . 

et ax . give approximation formulas to estimate the average 



d* 1 - : 



lys that result from this control policy. However, Pack 
roy suggests that when the volumes at an intersection are 
heavy, the arrivals are normally distributed. 

A critical intersection control scheme for a real-time 
control system is proposed in kef. 14, According to this 



20 

scheme, the cycle length remains constant for some predeter- 
mined period of time (i.e., 15 minutes) but the split changes 
according to the ratio Qa/(Q/\ + Q 3) on a cycle-by- cycle basis. 
The quantities Q^ and Q B are the critical queue lengths on 
the conflicting approaches measured by the detectors. 

Another approach to critical intersection control has 
been suggested by Gordon. Gordon does not attempt to mini- 

mize delay at the intersection but rather to maintain a con- 
stant ratio of the queue lengths on opposing approaches. The 
cycle length is assumed constant and the splits are changed 
according to the demand so that the ratio of the actual queues 
to the maximum link storage space on both phases are equal. 

The objective of control of all the previously discussed 
schemes is either to (a) minimize the total delays or (b) re- 
strict the queues as much as possible to prevent upstream 
intersection blockage. In trying to optimize the operation 
of a traffic signal, one would like to integrate the two 
objectives and develop a new control policy that both mini- 
mizes the delays and restricts the queue lengths at cversatu- 
rated intersections. This objective is accomplished in the 
subsequent chapters. 



CHAPTER 3 
INTRODUCTION TO OPTIMAL CONTROL THEORY 

3.1. Pre face 

The purpose of this chapter is to summarize the basic 
concepts of optimal control theory. Extensive development of 
the control theory is beyond the objectives of this chapter 
and the interested reader may turn to References 16, 17, 18 
and 19 for details that are not included here. 

Before discussing the basic concepts of the control 
theory, a simple example of a typical control problem would 
be instructive. A commercial airliner must fly at the alti- 
tude and speed set by air traffic controllers. Moving the 
passengers to their destinations is the objective of the air- 
liner. At the same time, the airliner must be operated within 
the limits that the aircraft and passengers can safely endure. 

The control problem in this example is that of designing 
the system so as to achieve the objecti\ r es while satisfying 
the operational constraints. Minimum time is the objective 
of the control, subject to safety constraints. 

Some systems arc so designed that once started they oper- 
ate without requiring further knowledge of the process devel- 
opment. Such situations are examples of open loon control. 
pen loop control is the simplest and the cheapest form of 



21 



n 



22 



control. It generally can be applied In situations In which 
performance standards are not very important, or whe re the 
operational mode of a system is fairly stable. It is only 
when performance requirements are introduced that open loop 
control fails. However, more elaborate control schemes are 
costly and the engineer must carefully examine the possibility 
of using open loop control before proceeding to consider the 
feedback concept and closed loop control. 

In the closed loop control, the desired operating point 
(state) of the system is measured and compared to the actual 
operating point. The difference of the two (error) is fed 
back to the input to bring the actua 



desired one. Thus closed loop 



tal operating point to the 
•oritrol requires determination 



(measurement) of the existing operating point of the system 
at various times. This point is a function of the control 
previously applied. Since ' the operating point is sampled at 
various times, the terminology "s amp led- data control" or 
"discrete control" is frequently used. As the sampling inter- 
val becomes large, the control approaches open loop control. 
Conversely, as the interval nears zero, the control approaches 
continuous feedback control. 

The various control problems are solved by mathematical 
optimization techniques. The objective of these techniques 
is to develop .rigorous procedures for optimizing a system 
that can be described mathematically. The nature of some 
systems is such that complete mathematical description is 
impossible, whereas other systems can be completely described. 



2 3 

Several approaches can be taken to the development of 
mathematical methods of optimization, all of which lead to 
essentially equivalent results. The variational method is 
most widely used. This method is based on the analysis of 
small perturbations and therefore lies closest to the usual 
engineering experience. The general approach is to assume a 
preliminary solution and then inquire about the effect of 
small changes. If the solution is in fact the optimum, any 
change must result in poorer performance. The precise mathe- 
matical analysis of this fact leads to necessary conditions, 
or equations, which define the optimum. Similarly, the 
analysis of the effect of small perturbations about a non- 
optimal solution leads to computational procedures which pro- 
duce better solutions. 

3 • 2 • O ptimal Control System Design 

Control, in the sense to be used in the following chap- 
ters, is concerned with affecting the physical behavior of 
systems. Control may be achieved by means of mechanical, 
electrical, electromechanical, electronic, and other devices 
which must function without direct human intervention or 
supervision . 

Obviously, the control of a system can be obtained in a 
number of ways. Usually the optimal one is sought. The need 
to control a system in an optimal fashion was the reason for 
the development of the optimal control theory and design. 



2 4 

Optimal control design methods utilize, as will be seen, 
state variables to describe the system and an index of per- 
formance (objective function)-. As a rule, the objective func- 
tion is expressed as a scalar function of the state and con- 
t rol vectors , i.e., 

t£ 

I = J F(x,u)dt (3.2.1) 

o 

where I is the performance index, and x and u are the state 
and control vectors, respectively. 

The only constraints imposed upon the solution are those 
related to the physical restrictions of the state and the con- 
trol vectors x and u. Furthermore, no assumptions are made 
as to system configuration or linearity of the control strategy 

By satisfying the physical constraints mentioned above, 
a u solution is sought, usually denoted as u . or u * , which 

Op L 

optimizes the index of performance. To solve the problem, the 
differential equation of the state vector x is required, i.e., 

x = f(x,u) (3.2.2) 

Depending on the nature of the problem, the state of the 
system at the beginning and the ending of the control period 
may or may not be specified. 

The only inconsistency that one may encounter in the 
above problem statement lies in the specification of the 
state at the end of the control period. One must make sure 
that the system is controllable and that the prescribed state 
is reachable. 



25 

The problem of finding the optimum control strategy- u* 
is,, in general, not an easy one. Only in very simple systems 
and for very simple I functions is it possible to obtain 
explicit solutions for u*. In most practical cases, one must 
be content with a numerical solution generated by a digital 
computer, which is incorporated as part of the system. One 
of the advantages of this numerical approach is that one is 
not limited to only those I functions which result in analyti- 
cal convenience. 

Optimal control methods can be applied to nonlinear and 
time varying systems. Furthermore, they incorporate all the 
advantages of the modern digital computers. That is, they 
leave the computational difficulties to the computer, allow- 
ing the designer to devote more time to analytical problems. 

Clearly, the objectives of the control depend on the 
nature of the specific problem. There are, however, some 
objectives in common with several optimization problems. For 
example, the objective of the control may be to bring the 
state of the system as close as possible to the zero state 
at a given time. This is referred to as the terminal control 
problem. Another objective could be to bring the state of the 
system to the zero state in minimum time. This is the minimum 
time problem. The objective of the minimum energy problem is 
to bring the state of the system to the zero state with mini- 
mum control effort. tn the pursuit problem, the objective 
is to bring the state of the system to a predetermined state 



26 

in a minimum time. The time at which the desired state is 
reached is called final time and it will be denoted lie re as t 



3.3. Th e Concepts of State and State Variables 

The concept of system is fundamental to optimization 
theory. One can speak of a system of equations or a physical 
system, both of which fall under the broad meaning of the term 
system. Systems are governed by rules of operation; they 
generally receive inputs and produce outputs affected by the 
inputs and the rules of operation. 

In addition to inputs and outputs and the rules of oper- 
ation, the state of the system is required for complete 
description. In some instances, the description of the system- 
can only be approximated, in others the description may be 
exact. To illustrate the concept of state, suppose that the 
equations characterizing a system are known; suppose also 
that outputs are to be determined which depend on the inputs 
and/or changes in the system after a certain time x. To 
accurately predict the response of the system after time T, 
knowledge of the state of the system after time x is the addi- 
tional information required. ■ The state at any time t is 
represented by the vector x(t) with n elements x (t) , x 7 (t) , 
...x n (t); one may interpret the n independent x variables as 
carriers of the full information about the transient states 
of the system. 

Direct control of the system is imposed by means of m 
control forces u, , ^ , . .,, Ujn , which are called control 



27 

variables. These control forces are applied by a controller, 
which always constitutes both the brain portion and the brute- 
force portion of the overall system. The controller takes 
proper control action based upon input or reference commands 
ana information obtained from sensors concerning the actual 
state of the system. The controller may be a human operator; 
the system is then manually controlled. In an automatic con- 
trol system a machine has replaced the man. 

Initially, at t = the total system state can be 
expressed by the n numbers x ] (0) , x 2 (0), ..., x (0). Under 
the influence of the m control forces and the inputs, the 
state of the system will change and thus the state variables 
are changing with time. Although the symbol x does not reveal 
it directly, each state variable as a rule has a very obvious 
p h y s i c a 1 me an in g . 

The evolution of the system in time can be described in 
terms of the changes of its state. Since these changes are 
usually affected by external inputs, it is convenient to 
represent the transformation in state by the transition 

SCV E(t3 S(t £ ) , ( 3.3.1) 

which is interpreted as: the state at time t Q is transformed 
into the state at time t f (t Q < t.,-) by the action of u(t) . To 
illustrate this idea, consider the set of ordinary differen- 
tia.! equations corresponding to the general continuous time 
fo rrn , 



28 



Ay 

3t" x l (t ' } = f 1 U 1 ,x 2J ...,x n5 V U 2"-->V t ) 

d^ . 

3t X 2 (t } ~ f 2 (x l » x 2 ' • • • ' x n » u l ' u 2 ' • • • » u m » t) 



dx 

n 



3t = X n (t} = f 5 (x l' x 2'---' x n' U l > u 2 ' " " " ' U m » ^ (3-3.2) 

where the x ± and u £ are functions of time t. As mentioned 
earlier, the state at any time t is described by the vector 
x(t) and the control is exerted through the vector u(t) . In 
vector notation the system of Eqs. 3.3.2 can be written as 

x(t) = f[x(t), u(t) , t] (3.3.3) 

where £ is a vector with n elements f f f 

Associated with the set of differential equations is a 
corresponding set of initial conditions which is Indicated as 

x(t Q ) - x(t-O) = x(0) (5 ^ 4} 

where it is assumed for convenience that t equals zero. 
The solution of the differential equations f. (i = l 3 2, 
. . . , n) is frequently called the trajectory of x(t) which 
starts at xfO) and passes through n- dimensional space up to 
X '-"M- The actual determination of such a trajectory may or 
may not be simple computational matter. When f is nonlinear 
It is necessary to turn to numerical techniques to evaluate 
the trajectory. 

When uft) = the system is called free or unforced. If 



F[x(t), u(t), t] - £~[x(t), u(t)J (. 



5) 



29 

where f does not contain t explicitly, the system is called 
stationary. Finally, if a system is both free and stationary 
it is called autonomous. 

3.4. The Performance Index 

The term performance measure or performance index is 

used to denote that which is to be minimized or maximized (to 
be extremized) . 

To measure the "goodness of control" in some meaningful 
manner, it is necessary to introduce a criterion which speci- 
fies how well the system is doing. This criterion is the 
performance index mentioned above. In alternative terms one 
needs to know how close the control achieves any goal which 
is set up for it. 

Selection of the performance index is not always an easy 

matter. As an example, suppose that one seeks to minimize 

the magnitude of a system error e 5 e (t) which is a function 
of time and is characterized by 

e - q(e,u,t) t& < t < t fe (3.4.1) 

where t & and t fe are specified, e(t a ) is given, q = q(e,u,t) 
is a given real valued function of its arguments, and u i u(t) 
is a bounded control action which is selected to attain mini- 
mum error over the time period defined by t < t < t . The 

a — — b 

manner in which the magnitude of c(t) is to be minimized is 



act obvious. One may cl 



y cnoose to minimize the integral of th 



e 



absolute value of the error over the closed interval it t !• 



a' n 






30 

or he may choose to minimize the integral of the squared 
error; or finally he may choose to minimize some other inte- 
gral of a positive definite function of the system error. 

Without loss of generality, in an optimal control problem 
it is required to extromize the scalar function l[x(0), t,], 
called the performance index, and expressed as 

n 
l[x(0), t f ] = _E Ci x.(t f ) = c'x(t f ) (3.4.2) 

where c' - [c, , c .„., c ] and the c . ' s are constants. The 

-L Li IX J_ 

notation here means that I depends on the starting value x(0) 
and the final time t,, In some circumstances the performance 
index is expressed in a different manner. 

There are a number of interesting points which require 
further discussion regarding Eq, 3.4.2. Since the origin is 
assumed to be the desired state, it follows that the terminal 
control problem is considered. If c, i = l,2,..,,n are taken 
as 1.0, the result is an unweighted, minimization of the devia- 
tion of the state at time t £ : bv setting some of the c's 
equal to zero these states are ignored since their deviation 
at time t f has no effect. Finally, it is noted that only 
those values at time t f , when the goal is reached, are in- 
volved; how this final state Is reached is unimportant in the 
sense that the trajectory actually followed is not involved 
i n th e p c r f o rm an ce i n de x , 

Although this performance index satisfies a number of 
important physical considerations, It does have the short- 
coming that the motion from x(0) ,0 to x(t ,.) ,t, is ignored 






51 

Th:Ls shortcoming can be improved if the performance index is 
redefined as 

t f 

I C x C0) ) t f ] = / f [x(t), u(t), t]dt f 3 4 31 

o J 

where f Q is a scalar function with the property that its 
integral is a positive number. In this manner the overall 
trajectory is involved in the minimization. 

It should be noted that when the f function of the sys- 
tem equations contains time explicitly, this time inclusion 
can be removed by introducing a new variable x (t) with the 
properties 

Vl (t] = X and x n +i(0) = (3.4.4) 

so that t can be replaced with j^. Thus the form f Q (x,u,t) 
is equivalent to the simpler form f Q (x,u), which may be used 
without loss of generality. 

In summary, the previous discussion suggests that when 
the system starts from a given state and time, x(0) and 0, 
the choice of u(t) automatically determines a trajectory of 
x(t) in x,t space. The choice of u(t) is usually subject to 
Upper and lcwer bound constraints (i.e., the control action 
is bounded). Of those trajectories, the "best" one is 
selected by comparing the values of the performance index. 
Thus, the performance index allows the selection of the 
optimal trajectory. 



32 

5.5, Pent ry agin ' s Maximum Principle 

In this section the maximum principle due to Pont ry agin 
and his collaborators ° will 'be presented, A rigorous proof 
of the maximum principle cannot be given without excessive 
mathematical development not justified here. A rigorous 
derivation based on geometric arguments is given by Pontrya- 
S in ®Ji M.- A more readable but less rigorous demonstration 

than Pontryagin's is given by Athans and Falb. 17 Other more 
simplified versions are given by Denn 10 and Coppel, 19 and the 
interested reader may turn to these references, to find the 
proofs that will not be included here. 

The maximum principle is applicable to both minimization 
and maximization problems since minimization of a function is 
equivalent to maximization of the same function with negative 
sign. Thus Pontryagin's principle can also be referred to as 
minimum principle if the objective is to minimize the per- 
formance index. 

It is convenient to explain the minimum principle by 
considering the following general control problem. 
Problem: Minimize the performance index 

tf 

C = U(t), t f ] - / f Q [x(t), u(t)]dt (3.5.1) 

o 

described by the n dimensional vector 

x(t) - f[x(t) , u(t)] (3.5.2) ' 

subject to the final cond'j Lions 



55 



g x U(t f )j - 



find the initial conditi 



i = 1,2, 



(s < n) (3.5.3) 



on 



x(0) = 



(3.5.4) 



The performance index is to be minimized by proper selec- 
tion of the control variables U][ , u £ , ... n^ . The control 
variables are not arbitrary but they belong to a usually 
closed and bounded set U called the control region or the 
admissible control domain. In the above problem the final 
time is not specified. It is then said that t c is free to 
l this formulation it is assumed that the functions- 



vary. I' 



L i (i _ L 5 2 » ••■> n ) as well as df./dx are continuous 



The solut 



ion 



proceeds by slightly reformulating the-prob 
lem by the introduction of the variable 



x Q (t) = f [x(t), u(t)] 



(3.5.5) 



■ith zero initial condition. The system is now of dimension 



n+1, i.e. 



x n > x i > X 9 ' 



It is noted th; 



p ^2 ' ' " " ' A n ' *«» as iiuLea inai if Eq. 3. 
includes t explicitly, t can be removed by defining a new 
variable 



x 



n+1 



t so that x (0) = and x , 
n i n + l 



= i 



(3.5.6) 



thus the dimension of the system Increases by n+2. 

To simplify the notation, the Hamiltonian formulation of 
classical mechanics is Introduced. 



he II ami 1 1 en i an fun ct i on 



is defined as 



34 

n __ 

H(A, x, u) = I ^(x, u) (3.5.7) 

where the variables \ n , X. a a arp fim r-t-i nn~ ^p +•■;«, 

0' i' 2' •'■' n x u iUn( -tioiii oi Lime 

and they are called adjoint variables. The adjoint variables 

are defined as 

V^ = \\ H 1 V 1 - 1 ' (3.5.8) 

] =0 i J 

From Eq. 3.5.7 one obtains 



ITT _ f i - x iCO i = 0,1,2,... ,n (3.5.9) 



and 



9 H n ^ ■ 

3TT = , E X j 7TTT i = 0,1,2,... , n (3.5.10) 

i j = u J 1 

From Eqs. 3.5.8 and 3.5.10 it follows that 

3H 



A (10 - 

J- d X ■ 

1 



i - 0,1,2,.. . ,n (5.5.11) 



In general, the minimum principle gives the necessary 
conditions for optimal solution of the problem. In fact, the 
principle states that if optimal solution exists, then there 
exists a nonzero vector T(t) satisfying Eqs. 3.5.9 and 3.5.11 
In addition, the following conditions must be satisfied: 

1. The optimal control u*(t) which minimizes 
1 -L x (0) , tf] must minimize the Hamiltonian 
£ un c t ion H at e a ch t i me point. 

2. If the final time tf is free, the minimum 
value of the Hamiltonian function H at the 
final time is zero. Also, A (t f ) < 0. 



inial trajectory 



furthermore, it can be shown that along the op- 

the Hamiltonian is a constant, i.e., II is equal to zero, not 

only at t f but also at any time in the interval [0, t r] . The 






35 



optimal solution must also satisfy the initial and the final 
conditions as well as the constraints placed on the control 
variables. 

In the previous formulation the values of the state vari- 
ables at the final time were not fixed. However, the same 
results apply to fixed final conditions x(t f ) . If the final 
state is the origin it can be shown that A n = 1.0. 

u 

Finally, it must be emphasized that In all the formula- 
tions to this point the final time t, is unspecified (free to 
vary). If t f is fixed the theory still applies with the only 
difference being that the constant value of H along the 
optimal trajectory is different from zero. 

If maximization of the performance index is considered, 
the optimal control u*(t) must maximize the Hamiltonian at 
each time point. Regarding the maximum value of the Hamilton- 
ian a few comments are in order. Frequently the maximum value 
is obtained by setting 3H/3u equal to zero; that is, by actu- 
ally differentiating the Hamiltonian with respect to u and 
setting the result equal to zero. In this differentiation, 
A and x are treated as constants. When u*(t) is Interior to 
any constraints, it is necessary that 3H/3u equals zero for 
maximum. This, however, is not true when the optimal controls 
are on the constraint boundary. 

There are a number of further important variations on 
the main theorem of the maximum principle. Of particular 
importance is the case where the state variables are con- 
strained over the entire trajectory. The complexity of this. 



36 

formulation, however, precludes presenting the details here. 
The interested reader may consult the references mentioned at 
the beginning of this section for further information on 
this point. 






CHAPTER 4 
SINGLE OVERSATURATED INTERSECTION 

4.1. Formulation of the Uncons tr ained Proble m 

At an isolated intersection serving n competing traffic 
streams, cars arrive at rates q. (t) (I = 1, 2, . .., n) . The 
arrival/rates are time varying but have a repetitive and pre- 
dictable pattern from day to day. The cars are discharged 
during the appropriate green phases; the rate of discharge 
during the green Interval is equal to the saturation flow as 
long as there is sufficient demand. When the queues dissipate 
the rate of discharge is equal to the arrival rate. If the 
demand is sufficiently low, there are no queues at the end of 
the green interval. The average green time per cycle is 
directly proportional to the average arrival rate and In- 
versely proportional to the saturation flow, i.e., 

57- ■ — + g i = i = l,2,...,n (4.1.1) 

i i 

where g. = the effective green time 
c = the cycle length 

q^ = the average arrival rate during the cycle 

5 ■ - t h e s a t u r a t i n f 1 aw . 
To. general, the policy followed by traffic analysts is to 
allocate the total available green time in proportion to the 

3 7 



3 8 

demand so that the same degree of saturation is allowed on 
all conflicting streams. That is, the effective green inter- 
vals must be selected such that the following relationships 
are satisfied: 



*1 



n 2 



S cr 
l to l 



S 2«2 



L n 
s g 



20 ^ 



(4.1.2) 



According to Webster,* the above relationship approxi- 
mately minimizes the average delay of the users at an under- 
saturated intersection. 

Consider that the demands at the intersection increase 

for some time period such that the capacity is exceeded and 

the intersection becomes overs aturated, For simplicity it 

will be assumed that there are only two competing traffic 

streams at the intersection and that without loss of general- 

:Lt >' s i is greater than s 2< The intersection becomes oversatu- 
rated when 



q- 



L > c 



q l ^2 ] 

or — - + — — > i _ i± 

S l S 7 c 



(4.1.3) 



where L is the total lost time per cycle. In this case, the 
theories that have been developed for- unders aturated condi- 
tions no longer apply since they do not minimize the total 
i n t e r sect i on de I ay . 

The peak period, as defined in this dissertation, is the 
time period from the beginning to the ending of queuing 'con- 
ditions on any approach to the intersection under considera- 
tion, fhe objective of the control, strategy is to minimize 









39 



the aggregate delay of both streams during the entire peak 
period. In developing the theory it will be assumed that the 
history of traffic arrivals at the intersection during the 
control period is known, and that the demand is not affected 
by the control decisions. These assumptions are fairlv r-^i- 
istic and have been used, previously 20 in the setting of pre- 
timed signals . 

Problem formulation is more easily understood through 
examination of Figure 2.1, in which the cumulative demand 
and service curves are plotted versus time for one approach.* 
The area between these curves from time zero to time T (the 
end of the overs aturated period) is a measure of the total 
delay to the users of the particular approach. The saw- 
toothed pattern of the cumulative output curve is caused -by 
the intermittent service of traffic by the signal. The verti- 
cal distance between the curves represents the queue length 
at a given time. The horizontal ' distance , such as t -t , 
represents the delay of the individual vehicle that joins the 
queue at time t ± and is serviced at time t ? . 

It will now be assumed that the saw- toothed pattern of 
the cumulative output curve can be represented by a straight 
line. This assumption is justified by the fact that the addi- 
tional delays caused by the saw-toothed pattern are negligible 
in cases of heavy overs aturation. The saw-toothed pattern 
can also he taken into account by shifting the curve G t 



.0 the 



*The notation and the formulation of the problem in this 
section aie those of Gazis.8 i " lx * 



40 



right by an amount equal to 1/2 (red Interval). The cumula- 
tive input and output in a time interval from zero to t ! arc 
given by 



Q(t) = / q(t)dt r 4 x 4 , 

o 

t' 

G(t) = / Y (t)dt f4 , 51 



Y(t) 



sg(t) 



c (4.1.6) 



where q(t) is the demand rate (slope of the input curve) and 



,ii:ie l. 



y(t) is the service rate (slope of the output curve) at t: 

It should be noted that the rate q(t) is time varying and 
is independent of the control decisions. If green time is 
tree to vary between a maximum and a minimum value, then the 
slope of the service curve y(t) Is also time varying, as shown 
in Figure 4.1. If g^ and g^^ are the bounds placed on the 
effective green time, then the service rate will also have 
upp e r and 1 owe r b o un ds de fined as 

r min c - ' ClJ - Sax = — F (4.1-7) 



The problem 



.em or optimizing the performance of the traffic 
ignal will now be formulated as an optimal control problem. 



suppose that, t L is t:he end of the overs aturation period: th 
2 t j 

i ] : '< - [ -J - (O -G : (t J IctL f.l I ;, 

i - 1 o J J " " 



Ti 



Q 1 ,G 1 



41 



Qi Ctl 




Q 23 g 2 



nuny 



Q 9 (t) 




Figure 4. 






42 



S J nCS V t}_G j Ct:) = X j Ct) = qusue l£ ngth at time t (on th< 
j ■ approach), Eq. 4.1.8 can be rewritten as 



D = 



2 T 

A f ^(t)dt / x (t)dt + / x 9 (t)d 
j=l o J 



o 



T 
/ 
o 



T 



=; - r [x, (t)+x ? (t)]dt 



The queue length x (t) can be expressed as 



f4 1 9 ") 



r ^s 1 
'11 



I 



t (4.1.10) 



XiOO - x 1 (0) + Q i ( t )-G 1 (t) = XjCO+Qj^Ct)- 

where x^O) is the queue length of approach 1 at time zero 
and has a constant value. Differentiating with respect to 
time, the following is obtained: 



dx 

dt 



1 « . dQ l s lSl 



+ 



dt 



q x (t)-u 



(4.1.11) 



where 



dO- 



q 3 Ct) - j^~ and u =■ Sj_ gl /c 

Similarly , 

* 2 (t) = x 2 (0)+Q (t)-G 2 (t) = x-(0)+Q,(t)- 



(4.1.12' 



S 7§ 



7&? 



t (4.1.13) 



ma 



dx 2 
dt 



+ q ? (t) 



2 g 2 



■ q 2 Ct) - -^ (c- gl -L) 



q 2 (t) - s 2 (l^-) 



S 2 g l 



q?ct) - s, ci-=-) 



S 2Sl S l 



c 



c s 



s. 



q? (t) - s o (1 -■=•) + — i 



(4.1.14) 






43 



If g max> g min are the u PP er and lower bounds placed on 
the effective green time g ± , then u will also have an upper 
and lower bound defined as 

(I) 



u 



mm 



c ff (l). 

1 mm l^niax 

— < u < u = L LdX 

c — — max c 



At the end of the overs aturated period (or final time) the 
queues on both approaches must equal zero, i.e., 



x i (t,) = x 7 (t,) = 



2 VU 1- 



(4.1. IS) 



Since the rush period begins at time zerc 



^(0) = x 2 (0) « 



(4.1.16) 



The minimization problem can row be stated using these deveT 
oped constraints and boundary conditions. 
Problem: Minimize the delay function 



D » / (x 1 +x 2 )dt 



with t, = free to vary (4.1.17) 



suo'iect to 



dx 



1 



dt 

dx 

ar 



£ 1 = q, (t) - u(t) 



2 



2 . - q 2 



(t) - s-U-fe + ~ u(t) 



(4.1.18) 
(4.1.19) 



w 1 1 h t h c b o un d a r y c o n d i t i o n s 



x ] (0) 



x.. ft, ) 



(4.1. 20) 



x, (0) 



"2 



f +■ 



(4.1.21 



44 



The function u is defined as 



u(t) 



5 lgl (t) 



(4,1.22; 



and is an admissible control in the interval 



s lS W /c 
l s mm 



u - < u < s , e w c = u 

mm - u - l to max /c max 



(4.1. 25) 



The problem may be restated using the following trans 
formations. Introduce a variable x n such that 



•0 



dx 







dt 



x, + x. 



(4.1.24) 



with initial condition 



x (0) - 



(4,1.25) 



and free final condition, i. 



■o 



(V 



= free to vary 



(4.1.26) 



The problem now takes the following equivalent form: 

Problem: Minimize the delay function (or performance 
index) D 



Min D 
u(t) ,t ] 

subject to 



1 J 



E Max F 



u(t) ,t. 



^ (t 1 3 



(4.1.27) 



dx, 



■0 "1 



+ x .-, 



(4.1. 2 3) 



at 



q-, CO - u(t) 



(4.1.29) 



45 

cbc, s 

3t~ = X 2 = ^2^ " S 2^ 1_ c^ + ~ U ^ t} (4.1.30) 

with boundary conditions 

x x C0) - x^) - (4.1.31) 

V°) = W = ° (4.1.32) 

x (°) ■ , x Q (t 1 ) - free to vary (4.1.33) 



and the admissible control domain 

1 min - i, < „ ^ l g max 

"c U min < u < — c = U max (4.1.34) 



and from here on the equivalent maximization problem will be 
considered. The above is an optimal control problem in which 

1. the system is the intersection. 

2. minimization of the total delay is the objective 
Of the control. The objective function is a 
function of the state variables at the final 
time tj defined as the end of the overs aturation 
period. 

3. x., ,x, are the state variables describing the 
system. 

4. u is a bounded control variable. 
5 - tj is an optimization variable. 
6. t is the independent variable. 

7 - x q is an artificial state variable. 

The problem can be solved by using Pont ryagin ' s maximum 
principle, explained in Chapter 5. The solution proceeds 
by introducing the Ilamiltonian function H 



fi = V : * X l f l + A 2 f 2 = L A i £ i C4.1 

i = 



, ae lined as 
Vi (4.1.0 






46 

where \., i = 0,1,2 are functions of time and they are called 
adjoi nt variables. For the optimality of the solution the 
adjoint variables must satisfy the following differential 
equations : 



dA 







SH 



dt 


3x 


dx 1 


3H 


dt ■ - " 


3x x 


dA ? 


3H 


dt 


3x 2 


Substitution 


of f 


yields 





(4.1.36) 



(4.1.3 7) 



(4.1.38) 



f ] , f- (Eqs. 4.1.28-4.1.30) to Eq. 4.1.35 



0' *1» "2 



H = A Q (x 1+ x 2 ) + X 1 [q 1 (t)-u(t)] 



X 2 [q 2 (t) - s (l-£) ♦ ~ u(t)] 



1 

and Eqs . 4.1.36-4.1.38 t ake the f o 1 lowin a form : 



(4.1 .39) 



□.a, 



dt 

dA. 

aT 

dA_ 
at 



= 



(4. 1.40) 
(4.1.41) 
(4.1.42) 



Because x Q (t^ is unspecified, the adjoint variable A at th 
final time must satisfy the condition 



w 



3F 



n ■ i J 



(4.1.43) 



ana since F = 



~ x n(^ 1 J, it follows that 



47 



VV = - 1 



(4.1.44) 



Integration of Eq. 4.1.40 gives 



^Q(t) - k Q = constant 



(4.1.45) 



and from Eq, 



4.4.44 it follows that 



K 1 



(4,1.46) 



Substitution of Eq. 4.4.46 into Eqs . 4.4.41 and 4.4.42 yiel 



yield; 



d^/dt = +1 and dA 2 /dt = +1 
Integrating Eqs. 4.4.47, one obtains 



(4.1.47) 



Vt) = t + k x 



(4.1.43; 



' an d 



A 2 (t) - t * k 2 



(4.1.49) 



where kj and k 2 are the constants of integration. Substitu- 
tion of Eqs. 4.1.44, 4.1.48 and 4.1.49 into Eq. 4.1.35 results 
in 



L. s ? 



H = C" 1 )Cx 1 +x 2 )+(t+k 1 )[q 1 -u] + (t+lc 2 )[q ? -s 7 (l-^)+-i u ] 



C s 



[-t-k 1 +Ct+k 2 ) i i]u-(x 1 +x 2 ) + (t+k 1 )q 1 



+ (t+k 2 )[q 2 -s 2 (l-|)J 

s 2 s 
- [(~-l)t+(k 2 -£- -k )]u 

1 z ' ~1 L 



L 



+ { ^l +c i2- s 2 (i -c )]t ^ X l +x 2 3+]c l^l +k 2^2- s 2^ 1 -c i)] 



(4.1. SO) 



48 
:his equation can be rewritten in a more simple form as 
H = zu + w 



(4.1.51) 



where 



So S 

2 ,w . „ 2 



Z = ( it- 1}t + (k 2 sT^V (4.1.52) 



'1 
an d 



L 



W = {q l + c l2- s 2 a -^ t-Cx 1+ x 2 )^ iqi+ k 2 q 2 -s 2 (l-|)}(4.1.53) 

Pontryagin's maximum principle 16 states that for optimal 
solution the following conditions must be satisfied: 

1. The optimal control u*(t) must maximize the 
Hamiltonian (Eq. 4.1.51) at each time point. 

2. Since the final time at the present problem 
is free to vary, the value of the Hamiltonian 
H at the final time must equal zero. Further- 
more H is constant and equal to zero not only 
at the final time but also for the entire 
control interval [0, t], 

The optimal solution can be obtained by proper determina- 
tion of the control variable u so that the above conditions 
are satisfied. From Eq. 4.1.51 it is seen that the Hamilton- 
ian H is a linear function of u, therefore 

3H/5u = z . • (4.1.54) 

In order to satisfy condition 1 as stated above, it is neces- 
sary to examine the sign of z which may be negative or posi- 
tive or, finally, it is possible that z equals zero. The 
optimal control u*(t) when z is greater than zero or when z 
is less than zero can be determined if the II versus u curv 



es 



are drawn (Figures 4.2 and 4.3). From Figure 4.2 



one can 



s i . 



verity that 






3H 

3u 



v— = z < 



u- = u 



mm 



49 



(4.1.55) 



Similarly, from Figure 4.3 it is clear that 



3H 

^— = z > ■+ u- = u 
ou max 



(4.1.56) 



: uations 4.1.5b and 4.1.5 6 are the results of condit 



ion 1 



according to which H must be maximized at each time point. 
However, when z equals zero conclusive results cannot be 
drawn by plotting the H versus u curve as before. In this 
case, the problem is solved by noting that z is a linear 
function of time. Therefore there will be at most one time 
point t at which z becomes zero. At this time point z chang 
sign, Without loss of generality it has been assumed that 
s 1 is greater than s 2 and the ratio s 2 /s, is less than 1. 
Then from Eq. 4.1.52 it is seen that the coefficient of t is 
negative , i.e., 



'2 /S l 



- 1) < 



(4.1.5 7) 



therefore z (t) is a straight line with negative slope, as 
shown in Figure 4.4. Figure 4.4 shows that in the interval 



L 



z is positive, whereas after this interval z is nega- 



tive. Consequently, at time t the o 
i.e. , 



F timal control is u - 

mm ' 



3H 

3u 



U" 



u 



mm 



(4.1.5 8) 



In summary, the preceding analysis indicates that 



if csli/'du 

is u* 



z is positive, the optimal control 



u 



max 



H 




3H/3u < 




I/3u 



> f) 



mm 



max 



u 



Figure 4. 



slope - (-£ -1) 

1 



T \ L 

Fi sure 4 . 4 






51 



lf on / du - z is less than zero, the optimal 
control is u* = u ■ 

mm* 

3. at the time point x at which 3H/9u = z becom t 
zero, the optimal control u* is switched from 
maximum to minimum. 



es 



The time point x at which the control variable u is 
switched from maximum to minimum is called switchover point, 
and the associated control bang-bang. The trajectory of u is 
shown in Figure 4.5. In traffic terms, this control implies 
that the effective green time g ± is maximum in the interval 
[0, x] and minimum in the remaining interval [x, t ]. Con- 
versely, since the sum of the green times is constant, g 9 is 
minimum in the interval [0, xl and maximum in the interval 
f T » t ±h Xt is important to note that the possibility that 
z does not change sign during the entire interval [0 , t ] 
should not be excluded. In this case, u* is either maximum 
or minimum, depending on the sign of z, for the entire inter- 
val [o, t 1 ]. 

It is clear that for the computation of the switchover 
time, the final time and the minimum delay knowledge of the 
demand curves is required. If the demand curves are linear 
functions of time of the form 

Q i = A i + V i - 1,2 (4.1.59) 

analytical solutions can be obtained as indicated in section 
2.2. This assumption, however, implies that the arrival 
rates are constant and not varying with time as it happens 
in reality. Furthermore, in the preceding analysis, no 



52 



u 



u 



A 
u 

L 


' 


max 
rain 






f 

L- J ^ 



Figure 4 . 5 

consideration was given to the maximum or minimum size of the 
queues. Therefore the solution (even for the linear demand 
case) may allow the queues to become negative before the end- 
ing- of the overs aturation period. A queue is said to be 
negative on a particular approach when the light is green and 
there is not sufficient demand. This situation should never 
be allowed before the ending of the oversaturation period. 
In addition to the lower bound, upper bound constraints must 
be placed on the queues so that upstream intersections are 
not blocked. The theoretical considerations and the solution 
to this more general problem are presented in the following 
sections . 



4.2. Op t i m al Con trol with S tate Var I a b 1 . e Cons traints 



In the previous analysis constraints we re only placed en 
the decision variable u(t) , Attention is now given to the 



53 

more general problem in which upper and lower bounds are 
placed on the state variables (queues). As mentioned earlier, 
the queues must always be nonnegative , otherwise green time 
is wasted. On the other hand, if the queues are allowed to 
grow with no restrictions, upstream intersections may be 
blocked. Consequently, congestion may spread to adjacent 
intersections even though the demand may be lower than the 
capacity there. In fact, the effectiveness of any control 
scheme lies in its ability to limit the queues to some 
desired level. 

This analysis will show that when both queues reach the 
upper bounds simultaneously, the cycle length must be free to 
vary. Thus, upper and lower bounds on the cycle length must 
be established. 

By considering queue length constraints, the problem is 
placed on a more realistic basis. The new formulation follows. 

Problem: Minimize the delay function 

Mm XQCtn) = Max F - -sq^i) = ~ f (x,+x ? )dt (4.2.1) 

u(t),t 1 u(t),t 1 o 

subject to 



ax, 

dt 
dt ' 



x + x 

"1 ^2 



£'-, = q-jCt) -u 



(4.2.2) 
(4.2.3) 



dx. 



tit: 



f-7 = C], -S„ (1- — ) +-— LI 

I -2 2 • C S , 



(4.2. 



with in.it 



and final conditions 



S4 



>^(0) - x 1 (t 1 ) - 



x ? (0) = x (t 



-> \ <• i ,' 

L 1 



x (0) - 



(4.2.5) 



(4.2.6; 



(4.2.7) 



u is an admissible control in the interval 

s,g (1) ■ s od) 

-i|^ = u . < u < ..l g ^x = u 

c mm — — c max 

and the additional state variable constraints 



(4.2.8) 



x. 



a, 



x > 



x, 



upper bound for queue 1 
upper bound for queue 2 



(4.2.9) 
(4.2.10) 
(4.2.11) 
(4.2.12) 



Optimal control theory states that if the constraints 



s tor 



any time interval are strictly inequality constraints, they 
do not place any restriction on the variation of the optimal 
control. One only needs to ash what changes are required when 
Eqs. 4.2.9 through 4.2.12 become equality constraints for a 
finit e period of time. That is, the equalities present a 
problem when they hold for a finite period of time. However, 
if they hold only for one time point they pose no problem, 
because the control variable is not affected. Therefore, 
when the bounds tend to be exceeded for some time interval, 



Eqs, 4.2.9 through 4.2.12 become equality constraints 



, J - • - • 3 



a l 


or 


■ :> 1 


X - Ct ~ 

X I 1 





a ? 


OI 


S 7 = 


x ? -a ? - 






(4.2.13) 
(4.2.14) 



x, - or S- = x, -0 = x, 

1 3 11 



x 



or S. = x ? -Q 



x. 



(4.2.15) 
(4.2.16) 



To simplify the analysis, first consider only equality con- 
straint 4.2.15. Afterwards, extension to include the remain- 
ins constraints is simple. 



Consider an interval [t 



(1) A2\ 



] during which the opti 



mal trajectory of x, lies along the constraint (see Figure 
4.6), Since Eq. 4.4.13 holds as an identity, i.e., it is 

true independently of the value of t in the interval [t^ , 

f 2 1 

t ], it can be differentiated with respect to time to obta: 



but 



dS. 



at 



dx- 
dtT 



dx. 
aT 



q r u 



(4.2.17) 



(4.2.18) 



and so 



q, -u = 



t CD <t<t (2) 



(4. 2.19) 



Therefore, Eq. 4.2.19 must be satisfied for every time in the 
interval [t l ~ J , t ^ J ] where the equality constraint 4.2.15 
holds. In addition, it is required that (see Figure 4.6) 



SjttW) - , ctW 



) - a - 



(4.2.20) 



That is, when Eq. 4.2.20 is valid, Eq. 4.2.19 or its corre- 
sponding Eq. 4.2.13 'is valid for the entire time period [t^ ■ 



(2) 



]. Therefore, Eqs, 4.2.19 and 4.2.20 are equivalent to 
4.2,13. 



i>0 



X. 




t 



CD 



(2^ 



Figure 4.6 



For a problem having equality constraints such as 4.2.19 
and 4.2.20, the differential equation for the adjoint vari- 
able A, is given by 
1 & J 

2 ('. 



dX. 



i = 



d r 



x 3fj r3R x1 -1 3R X 



3 x , 9 u [ 3 u J 



dX- 



X. 
J 



(4.2.21) 



Furthermore, at time t = t 



(1) 



:he adjoint variable X 1 should 



satisfy the fallowing condition: 



(4.2.22) 



and since 3S-/3X, = 1 (see Eq. 4.2.20), it follows that 



\ 1 (t (1) -) - A l( t^ + ) ♦ y 



(4.2.2 3) 



where A, is a constant to assure the discontinuity of the 
trajectory of A, in the vicinity of t' ^ (see Figure 4.7), 
This condition is unique if it is required that X be con- 



tinuous 



5 7 

Similar analysis applies if equality constraint 4.2.14 
holds and equations such as 4.2.20 and 4.2.22 need to be 
derived. - . 

Consider an interval [t^ , t ^ J ] during which the opti 
mal trajectory x~ lies along the constraint 4.2.14 (see Fig- 
ure 4.8). Since Eq. 4.2.14 holds as an identity for every 
time point in the interval [t^, t *- ^ ] , it can be differen- 
tiated with respect to time to get 



dS „ dx ? 

a"t~ " 



dt 



= 



DUG 



dt 

therefore 



dx ? , s ? 

' * q -s (l-|) +? £ u 

L £ C S 1 



R 7 



q 2 -s 2 (i-!) + Jf u = ° 



t (3) <t<t (4) 



(4.2.24) 



(4.2.25) 



(4.2.26) 



A, 



/ 



y 



/ 




^x 1 (t (1) ") 



t^ 



Figure 4.7 



58 




Figure 4. 



Thus, Eq , 4.2,26 must be satisfied for every time point in 
the interval [t- , t L ; ] where the equality constraint 
4.2,14 holds. In addition, it is required that 



S^t^) = x 2 (t^)-a. 







(4.2.2 7) 



That is when Eq. 4,2.2 7 is valid, Eq. 4,2.26 or its corre- 
sponding Eq. 4.2.14 is valid for- the entire time period [t^ 

f'4 1 
t l •' ] . Therefore, Eqs . 4.2.26 and 4.2.2 7 are equivalent to 

Eq. 4.2.14. 

Because Eqs, 4.2.26 and 4.2.27 are equality constraints, 

the differential equation for the adjoint variable X-, is 

given by 



dX, 



a~t 



1- - T. 



3±„ 



3 f . (dR^-\. -1 3 R, 



3u Du 



"2 J 



] 



Also, at the point t = t^ ' the adjoint variable X- must- 
satisfy the following condition: 



(4.2.2 8) 



59 



M' 



(3) 



(3) 



3S. 



3 - * 2 Ct^ ) + U 2 3-±. A ? (t^^) + u (4.2.29) 



rt^) 



where u 2 is a constant assuring the discontinuity of A ? at 
the vicinity of t - J . 

Equations 4.2.21 and 4.2.23 must be satisfied only when 
constraint 4.2.9 is imposed. Equations 4.2.2 8 and 4.2.29 
must be satisfied only when constraint 4.2.10 is imposed. 

The differential equations 4.2.21 and 4.2.28 require 
further expansion. Equation 4.2.21 yields 



2t ~TiT du [ 3u j dxl 



u) 



A 



f3[q- L (t)-u] 3[q 1 (t)-u] (3 (q- [ -u) ) - 1 3 (q n - u) 

j 3x^ ' du ~ 



dU 



h 



f ^c^Ctj-u] 3[q 2 ( t )-s 2 Cl-|) + ii u] 



3x- 



3u 



fH^-ujyl 3(q 1 -u)) 



• u 






[o-o(-i) " oj-A n - [o-C-D(-i)" 1 o] 



1 m.i 



co-(~-)(-ir 1 -co)]-x 2 



= ° (4.2.30) 

Therefore \- } (t) is constant in the time interval [t^ 1 ^, t^] 

Similarly, from the differential equation 4.2.2 8 it follows 
that 






6 



dA 



/ ■ -[o-o(--i)' 1 o]a. [o-c-DC^-)" 1 o]a 1 



'1 

[O-(^)' (--)'" 0]A, = 

1 1 " z 



'1 



(4.2.31) 



Therefore A„(t) is also constant for the time interval [t 

(4'1 , 
t ] . 



(3) 



The previous analysis is also valid for the lower bound 
constraints 4.2.11 and 4.2.12. In fact, by inspection of 
Eqs. 4.2.13 and 4.2.15 it is seen that S ^ can be obtained from 
Eq. 4.2.13 by letting a, equal to zero. Thus, the results 
obtained for the upper bound constraint 4.2.9 are also appli- 
cable to the lower bound constraint 4.2.11. Similar conclu- 
sions can be drawn for the lower bound constraint 4.2.12. 

In summary, the preceding analysis indicates that 

1. When constraints x-j_ <_ cti or xj > are 

imposed 

a. the optimal control u* is affected only 
when the constraints are at equality for 
some time interval [t(l), t(2)]. 

b. during this interval Ax (t) is constant 
and is given by Eq. 4.2.2 3. 

c. from Eq. 4.. 2.19 it follows that when the 
constraints are at equality 

u* = q 1 (4.2. 32) 

2, When constraints x? < a? or x 9 > are 
imp os ed 

a. the optimal control u* is affected only 
when the constraints are at equality for 
some time interval [t( 3 ), tC^3j. 

b. during this interval A2 (t) is constant 
and is given by Eq. 4.2.29. 

c. from Eq. 4.2.26 it follows that when the 
constraints are at equality 

u ; - - [s 9 (l-~0-q,] — (4.2.33) 

C -L b ? 



61 

If two constraints are of equality simultaneously, I.e. 
if it is required to satisfy 4.2.9 and 4.2.10 simultaneously 
and the cycle length Is constant, the problem may be impos- 



sible. This is because In th: 



as e Eqs . 4.2.32 and 4.2.33 



rasp 



trust be satisfied simultaneously, I.e., 

s. 



U" 



q 



L. 



1 



LS ? (l-~)-q ? ] 



1 

c J H 2- ! sT 



(4.2. 34] 



or, solving for c, 



1 



qj q 7 



2 



(4.2.35) 



• j 



if the given constant value of the cycle length satisfies the 
above relationship, a solution exists and both constraints on 
x ~i an -d x ? can be imposed. If not, a solution does not exist 
and the constraints will be violated. Equation 4.2.35 simply 
implies that a solution exists only if the signal is not 
oversaturated during the period at which both constraints are 
at equality. 

In order to circumvent this difficulty, the cycle length 
must be free to vary so that 4.2.35 is satisfied. In this 

case, a maximum and a minimum value (c and c . 1 for thp 

k max miru 

cycle length need to be established. If only x is on the 

equals zero or if x. equals 



ounda r i e 



tha 



s , 2 j: eit ner 



tnen considering 



i- x 



1 ■ I 



!C V. b .-> 



ou con 



62 

must change correspondingly so that 4.2.36 is satisfied. 
Similarly, if only x« is on the boundaries, then from 4.2.35 

t 

s 2 (L+ gl ) 

C sT^ (4.2.37) 

b 2 l 2 

an-" since c, s,,, and L are assumed constant, g, must change 
sc hat 4.2.37 is satisfied. From 4.2.37 it is seen that if 
s 2 is less than or equal to q ? , a solution does not exist. 
This condition simply implies that the input flow rate is 
higher than the saturation flow at the second approach.- Conse 
quently, congestion cannot be avoided even by providing con- 
tinuous green. Therefore, it is possible to impose only one 
constraint and keep the cycle length constant; however, for 
more than one constraint, it is necessary to have variable 
cycle lengths. Clearly, when constraints are imposed, several 
switch points may exist. The number of the switch points is 
a function of the demand curves. 

It is emphasized that in the preceding analysis, no 
specific assumptions have been made concerning the demand. 
Thus, the theory is general and applicable to any demand func- 
tion. Furthermore, it must be noticed that control with upper 
bound constraints prevents upstream intersection blockage but 
results in higher total delay. When minimization of the 
total delay is the only objective of the control, upper bound 
constraints should not be placed. Solutions of both the 
unconstrained and the constrained problems are necessary at 
th i s po'i lit . 



4.3, So l ution, to the Unco nstrained Proble m 

The problem of finding the optimal control u* is , in 
general, not an easy one. Only in very simple systems is it 
possible to obtain explicit solutions for u*. The situation 
becomes more complex when nonlinearities are introduced, and 
in most practical cases one must be content with a numerical 
solution generated by a digital computer. It is then neces- 
sary to develop an algorithm to calculate the switch points 
(if they exist), the final time and the minimum delay. In 
this section the minimization problem with, only lower bound 
constraints will be considered. When upper bound constraints 
are imposed, the resulting delays are higher and the control 
becomes more complex. This case Is treated In the next section, 
The algorithm for the unconstrained problem is as follows: 



STEP 1. Assume values for k-, and k ? 



The unknown integration constants k-, and k ? of Eqs 



4.1.48 and 4.1.49 are needed for the computation of th 



e 



adjoint variables A, and A„. Based on the estimated values 
of k, and k~ an initial solution can be found. The optimal 



solution will be computed by Iterating on k 1 and k 



2 



STEP 2. Set t 1 = 0, x n (t x ) - 0, x, (t 1 ) - 0, x^ft 1 ) - 



an d 1 = . 



The initial conditions of the state variables x,,x ? , i. 
:he queue lengths and the total delay x„ are zero as stated 



iii the formulation of the problem 



64 



STEP 3. Put i = i+1 , t*- 1 -' - t^+At and 



AoCt 1 ) = -1 
A^t 1 ) - t (: 
X (t X ) = t (l) +k. 



X^t 1 ) = t^ + k 1 



This step performs numerical Integration of the adjoint 
variables (Eqs . 4.1.40 through 4.1.42). 

STEP 4. Find the value of z at t 1 from Eq. 4.1,52, i.e., 

i - c^.- Dt (i) ♦ (k 2 !i. kp. 

STEP 5. Examine the sign of z. 

If z > , ■*• u* = u 

' max 

I £ z < , ■+ u' :; = u 

— ' hi in 

If at t'-~ - ; z > and at t K } z < 0, set t = t 1 -' 

ks Indicated in section 4.1, switchover point occurs 
when z changes sign, and the optimal value of u at each time 
point is determined from the sign of z. 

STEP 6. Determine the current state of the system. 
j X 1 (t Ci) );» x^t 11 " 13 ) + [ qi (t Ci) )-u*]At 

* ? (t (l) ) - x (t (i " 1} ) + [q 2 Ct (i) )-S 2 (l-fe + ^- u *]At 

x (t (i) ) = x (t (i_1) ) + [x 1 (t Ci} )+x 2 rt (l) )]At. 

This step performs numerical integration of the state 
equations 4.2.2, 4.2.3 and 4.2.4. if any of the state vari- 
ables are negative, steps similar to steps 2a, 5a and 6a of 






65 

the constrained algorithm (next section) must be followed for 
the calculation of the adjoint variables and the control vari- 
able u. 

STEP 7. Examine the value of H at time t ^ , i.e., 

f i 1 

Is H(t v J ) = zu*+w = 0? 

If "yes" go to Step 8. 

It "no" put t = t +At and return to Step 3. 

In this step the value of the Hamiltonian function Is 
checked to determine whether or not it is constant and equal 

to zero along the entire optimal trajectory. If H Is zero at 

( i "! t 1 ~\ 

but not at t , the assumed k ± and k ? are wrong and new 

values must be given. Conversely, if H Is zero for the 
entire interval [t^, t^], the k ± and k £ values are correct 
Equation 4.1.51 is used to compute H. 



STEP 8. Examine the state of the system at t^ 1 ^ 
Is x 1 (t^ 1 ^) *» and x ? (t^) = 0? 



, i.e.., 



If "no" and H(t (rj ) = o, return to Step 3 



"^ ,-. 1 1 



>r HCt^) j 0, put t, » t^ , 



no" or H(.t v J ) f 0, put t 1 = t^, total 
delay = x (t^ 1J ), assume new values for kw and k ? 
and return to Step 2, 

If "yes" and H(t Cl) ) - 0, END. The total delay 

f i 1 ( ' ~\ 

is x (t l J ) and the final time equals t lLJ . 



This step assures that the optimal values of k, and k„ 

i- 2 

have been found and terminates the iterative procedure. If 
]: l and k 2 are not the optimal, new values need to be assumed 



66 



and the process is repeated. The new values of k, and k ? , 

th 
however, will not be random in the 2nd, 3rd, ..., n " itera- 
tion, but they will be chosen by an optimization routine. 
The routine will minimize the objective function 

7 ? 



I 



X 9 \t~ J 



Therefore, this step is the responsibility of the optimization 
subroutine. The reason for using the sum of squares of the 

queues at the final time in the objective function is due to 

2 1 

the fact that this function is quadratic. Powell has shown 

that such functions result in faster convergence. 

It should be noticed that the above algorithm ends only 
when the conditions of Pontryagin ' s maximum principle have 
been satisfied. That is, the algorithm assures that the 
Hamiltonian function is constant and equal to zero along the 
optimal trajectory; furthermore, H is maximized with respect 
to u at each time point. The initial and final conditions 
are also satisfied since the queues at the beginning and 
ending of the control period are zero (Steps 2 and 8). Fig- 
ure 4.9 illustrates the algorithm for further clarification. 



4.4. Solution to the Constrained Problem 

In the previously developed algorithm no upper bounds 
are placed on the state variables x, and x- (queues). There- 
fore, the algorithm is not applicable for cases where minimi- 
zation of the total delay subject to queue length constraints 
is the objective of the control. Constraints can be placed 
cither on one or both queues; in the latter case the control' 



ENTER WITH: 

1 » 2 ' 

(INITIAL VALUES) 



OPTIMIZATION ROUTINE 



K 1' K 2 



.^S 



-Ah' 

x ? (t 1 ) 



OPTIMAL CONTROL 
ALGORITHM 

(STEPS 2-7 INCLUDED) 



Figure 4.9 



>• K 



i >^7 



JX-, i 



(optimal) 



-> I 



->-T 



'1 

>Tot 



delays 



is more complex because the queues may be at. the upper bound 
simultaneously. In the development of the algorithm, the 
necessary conditions for optimal solution derived in section 
4.2 will be used. Since the problem of constraining one 
queue only is simpler, it will be considered first. 

In the following algorithm It is assumed that constraints 
are imposed only on the first queue, i.e., 

< x, (t) <_ a. 

If constraints arc Imposed only on the second queue, the 
algorithm still applies with some minor modifications. These 
modifications wil-1 also be presented. The new algorithm is 
as fol lows : 



6 8 



STEP 1, 
STEP 2 . 



Assume values for kj_ and k ? . 



be" 



- 0, Xg{t j 



0, x,(t Ci] ) 



x ? (t^) = and i 







These ti\ r o steps are the sane as the ones of the previous 
algorithm. 



<J x lli t ij cl i 



Cb° 



iecK the magnitude of x. 



Ci) 



>(i) 



If x 1 (t^ J ) > c^ or x x (t^ J ) £ put u» 



q- 






a-, or x, = and if u . < u* < u 
1 2 mm — — max 



go to Step 3a, Otherwise, the problem is 
impossib le . 

That is, when the constraints placed on xy are active, the 

optimal value of u is not determined from z but rather from 

Eq„ 4.2.32., If the optimal value of u lies outside of the 

bounds specified for u, solution does not exist because the 

constraints placed on u are violated. A suboptimai policy 

would be to use either u when u* > u , or u - when 

max max' mm 



u" < u 



mm 



STEP 3, 



Put 



1 + 1, t 



:d = t (i) +At 



At and 



1 



\ v Ct (i:) ) - t (i3 + k 
x 2 (t (i) ) = t^+k 

and go to Step 4. 



m: 



;ep is the same as j,n the previous algorithm and is 



Followed only when x, is internal to the constraints 



69 
otherwise it is bypassed. 
STEP 3a. Put i - i+1, 

and go to Step 6. 

This step is followed only when any of the constraints placed 
at x ± are at equality; the value of u* has been determined in 
Step 2a. The value of A, is maintained constant. 

STEP 4. Compute z. 

1 " s l x 

STEP 5. Examine the sign of z. 

If z > + u* = u 

max 

lfz<0+u*=u.. 

— mm 

If at t^ 1] z > and at t^ z < , set t - t^ 

These steps are the same as in the previous algorithms and 
they are bypassed when Xj is either at the upper or at the 



lower bo un 



A 



STEP 6. Determine the current state of the system. 



^(j-)'i _ v r+ (i-l)-» . r ,-.('i)^ n L,. S 2 

j ~ X ?^ L j T [q?U* 0-s 2 Ci--) + ~ u*]&t 



c 

i. 



V tCl b - xoct"-") * tx^t^h^ct^h 



70 



This step remains unchanged and it is always followed. 



STEP 6a. Check the magnitude of x. 



If x, > a, or x, < put 
(1) _ ,(i) 



t - L 



and 



(I) 



^(t^O = A^t^)^- 



This step satisfies the jump condition for A, at t^ •* . In 



addition , X is maintained constant in the interval [t 
t v j . hquation 4.2.2 3 is used for the computation of 



CD 



(i) 



XjCt^). 



?EP 7. Examine the value of H at time t'- 1 -' 



is h = v ) (x i +x 2 ;)+x i [ci r u]+A 2 [ci 2" 5 2 cl -c 1)+ r 1 ll] = 0? 

If "yes" ?o to Step 8. 



it "no" put t 



: (i) +At a 



nd return to Step 2a. 



The Hamiltonian function in this step is computed from Eq. 

r li r 9 1 

4.1.39 since A, is constant in the interval [t v , t K ^ J ] and 
Eq. 4.1.51 does not apply. 



STEP 8 



Examine the state of the system at t ^ , i 
Is x, (t^h = and x 2 (t^) = 0? 



fll 

and H(t. J ) = 0, return to Step 3 

If "no" or H(t^) f 0, put t. 



t^ , total 



CD 



delay = x (t^ J ) , assume new values for k, and k ? 

and return to Step 2, 

if "yes" and BCt^} - 0, END. The total delay 



X ^ 



• .) and the linai rime equals t v 



71 



This step is the same as in the previous algorithm. 

When this algorithm ends, it has satisfied the necessary 
conditions of the maximum principle, since H is constant and 
equal to zero. The Hamiltonian function has also been maxi- 
mized at each time point. The constraints are not violated 
since u* is determined from Eq. 4.2.32. Furthermore, X. main- 
tains a constant value during; the period at which the con- 
stramt is at equality, and the jump condition of section 4.2 
is satisfied. 

When only the second queue is constrained, the algorithm 
still applies but Steps 2a, 3a and 6a need to be modified as 
follows . 



STEP 2 a. Check the magnitude of x 9 , 

s. 

1j -i 1 L 



If x 2 > a 2 or x ? <_ 0, put u* = [s, (1--) -q, ] — 



C z J s 



If U min i U * i U max ^ ut X 2 = a 2 or X 2 = ° 
and go to Step 3a. Otherwise, the problem is 

impossib le . 



STEP 3a. Put i i+1 

■o 



.(t (iJ ) = 



and go to Step 6 . 



STEP 6a. Chech the magnitude o £ X-, 



4- K. 



r i 'i r 



u J 



(t (i) ) 



A 7 (t f 






or x < put 

d.u CI 






72 

If constraints are imposed on both queues and the con- 
straints are at equality simultaneously, the cycle length must 
be free to vary. During this, period the. following steps must 
be followed. 



STEP 2a. Check the magnitude of x, and x 9 . 



L, 



If x, > a, and x n > a n put u* = q, = [s~ (1~— ) -q_ ] — 

1—1 2 — 2 r l l 2 - c L 2 J s_ 



If u 



mm — ' "max c ~ ~^1 """1 **""' "2 "2 

and go to Step 3a. Otherwise the problem Is 

impossible . 

If only x, > a, follow the algorithm developed for 

constraining the first queue. 

If only x~ > a ? follow the algorithm developed 

for constraining the second queue. 



STEP 3a. Put i = i+1 

x Ct^D - 



x 1 Ct (i) 3 = x.Ct^' 1 ^ 



l 
i 



x 2 (t (i} ) - x^ 1 " 1 ^ 

and go to Step 6. 



STEP 6a. 



Check the magnitude of x, and x„ 



If x 



1 



'1 



put \. (t Uj ) = X, (t 



1^ J ' "1 



If x ? > a,., put A- (t 



Ci), 



f x, > 



and x- 



= x 2 ( 

put c* 



t(i)l + 



J ' Vn 



l-LCq 1 /s 1 )+(.q 2 /s 2 T 



I f c - < c* < c 

mi n — 



the problem Is 
m ax L 

possible. Otherwise the problem has no solution. 



75 

It is possible that during the control period the con- 
straints are not at equality simultaneously. In this case, 
the cycle length can be kept, constant for the entire interval 
[0, t 1 j. 

4,5. Some Computational Aspects 

The computation of the adjoint variables A, (t) and A 7 (t) 
for the constrained problem requires further development. In 
section 4.2 it has been shown that \A£) and X n (t) are con- 
stant when the constraints are at equality, and that as soon 
as the bounds are reached there is a jump condition that the 
adjoint variables must satisfy. The constant value of the 
adjoint variables given by Bqs . 4.2.2 3 and 4.2.29 can be com- 
puted only If the parameters y and y„ are known. Since the 
derivation of u, and y. ? is not apparent, it is presented in 
this section. 

A closed form solution for u, can be found from Eq. 
4.2.23 and Figures 4.6 and 4.7. At time t *• ' it is required 
that the adjoint variable A, be continuous, i.e., 



Mt t2 >") - M t(2) + ) 



(4.5.1) 



and since A, is constant in the Interval [t^ ■ ', t- 2 - 1 }, it 



'1 

follows that 



^(t (1)+ ) 



X l (t 



(2) 



(4.5 



Furthermore, Eq. 4,1.48 at times t 



(2) 



Uld t ' J 



y i elds 



However, from Eq. 4.2.2 3 



or, substituting A., (t v -' L -' ) into Eq . 4.5.5 



^-1 int. 



thus, from Eqs . 4.5.2 and 4.5.6, 



and, finally, from Eqs. 4.5.3 and 4.5.7 



74 



, f 2 1 f 2 1 



and 



V tO>) - tCD.i 



1 



(4.5.3) 



(4.5.4) 



A 1 (t (1)+ ) + u 1 



"1 



1 



(4.5.5) 



V (I), i - t cl} -Vi 



(4.5.6) 



Mt (2 b 



t +k x p 2 



(4.5.7) 



t^ 2j +k 1 = t^+k.-^ 



(4.5.8) 



u 1 - t 



(D„ t (2) < Q 



'4.5.9) 



Similarly, y 9 (considering Eqs. 4.1.49 and 4.2.29) Is given b' 



u ? . t^-t^ < 



4.5.10) 



Thus, the final form of Eqs. 4.2.2 3 and 4.2.29 becomes 



) ft^^l 
A 1 (t 



x lt t")-) 



t (D t (2) 



(4.5.11) 



an d 



X 7 (t 



(3) 



J + t 



(4) 



(4.5.12) 



75 

Faster convergence and a more accurate solution can be 
obtained by estimating the parameters k-, and k ? which are 
required in the first step of the previous algorithms. Since 
however, k, and k« have no physical meaning, it is difficult 
to be estimated. Nonetheless, if estimations of r and t 1 are 
made, k, and k~ can be derived from Eqs . 4.1.50 and 4.1.52 by 
setting z equal to zero at time x and H equal to zero at time 
t, . In this manner, a system of two equations with two 
unknowns, k-, and k ? , is obtained which can be solved for k, 
and k„. In fact, letting Eq. 4.1.52 equal zero at t = t the 
following is obtained: 

s . s 

(—- - 1) + (k 9 -1 - k ) = (4.5.13) 

1 l s l l 

and from Eq. 4.1.50 at t = t 1 

s 2 S 2 L 

(g l)t x u + (1< 2 — -k x ) - [q 1 + q 2 -s 2 (l--)]t 1 - x 1 

- x 2 + k iqi + k 2 [q 2 -s 2 (l-|)] = (4.5.14) 



The solution of the above system (Eqs. 4.5.13 and 4.5.14) is 

(4.5.15) 



ocu+ (a/f ) y - 6 1 , - ( f - 1) t , u 



"1 ~ VCY/fJ 

k 2 = (k 1 -a)« (1/f) (4.5.16) 

a = [ ( s ,, / s -, ) - 1 ] t an d f = s - / s n 

£ J. £ X 

Y = q ? -s ? (1-L/c) 

5 = qi +q 2 -S 2 (l-L/c) 

u - u, 



mxn 

1 nu y a t a ~ a t +■ -~ +■ 



q. ,q» = the flow rates at t = t 



7( 



A final remark is in order before concluding this sec- 
:ion. From the relationship 



s - s ? 
z = (—- -Dt 1 + (k ? -± 
1 1 



k,3 



(4.5.17) 



and since it was assumed that s, is greater than s,, it 

JL 6 

follows that the first term is always negative. Therefore 
z changes sign onlv if 



s s 

:, — - k, is >0 -> k > k., -± 

2 s 1 2 1s 



(4.5.18) 



Otherwise, z is always negative and switch point does not 
exist. When s, is equal to s ? , switch point does not exist 
since z will always have the sign of the second term. 



4,6. The Optimum Cycle Length 

The cycle length c is a parameter which remains constant 

throughout the entire peak period. The total intersection 

delay is a function of the cycle ' length , and the problem is 

to find the optimal value of c that minimizes the total delay. 

For practical reasons the cycle length has upper and lower 

bounds so that c - < c < c . Short cycles create excessive 

mm — — max 

lost times which, in turn, cause extreme delays. Long cycles 
may be ignored by drivers who can possibly think that the 
s i gn al h as failed. 

In general, experience indicates that for overs at ur a ted 
intersections and for single setting of the signal, long 
cycles result In less delay. This is justified by observing 
that as the cycle length increases the number of cycles 



77 



during the peak period decreases and the total lost time 
de ere ases . 

In fact, if p is the percentage of' green time G, given 
to the first approach, then the effective green time is 



a - pc 



(4,6.1) 



where &, is the lost time spent for acceleration and clearance 
The output rate per unit of time Is given by 



Y 



S O" 
1°1 

c 






c 



(4.6.2) 



The above equation verifies that as the cycle length Increases , 
the output rate (slope of the cumulative output curve) in- 
creases since the ratio Z,/c decreases. Similarly, for the 
second approach the effective green time g ? is 



g ? 



= (l-p)c 



(4.6.3) 



tli us the output rate 

[(I" ! 



S <T 
? °? 



? can be expressed as 
%. 



2 



^2 



(4.6.4) 



hence y 9 also increases with Increasing c. Therefore, the 
total output rate (Yi + Y?) io r the intersection increases when 
c increases. The final time, however, decreases as the total 
output rate increases and the area between the total input- 
output curv"es_ (i.e., the total delay) decreases. Thus, it 

v;d that for single settings of the signal, 
umizes tin* total delay i.s the maximum 



has been ostao.1 



7S 



allowable cycle length. The interesting question is whether 
or not the same principle holds true when the optimal control 
strategy is to be considered. This question can be answered 
by using the results of the previously developed theory. In 
sections 4.1 and 4.2 it has been shown that the optimal con- 
trol strategy results in less total delay than the single 
setting strategy. Consequently, the aggregate delay must 
also decrease with increasing cycle length. The only compli- 
cation may arise when the cumulative output curves happen to 
intersect the demand curves before the end of the peak period. 
In this case, it was shown that the optimal control is to 
switch at the point of intersection so that no negative queues 
(therefore, slack time) are allowed. The resulting delay is 
again lower than that of the single setting strategy, demon- 
strating that the maximum cycle length minimizes the total 
delay,. The above results are illustrated by an example in 
Appendix 1. 






CHAPTER 5 
OPTIMAL CONTROL WITH BUS PRIORITIES 



5.1. Statement of the Problem 

Reduction of bus delays at signalized intersections is 
one of the major problems associated with bus transportation 



-\ 



22-25 • r • 

today. Previous studies • have shown that significant 

delay savings can be obtained by introducing exclusive bus 
lanes and/or by granting priorities to the buses at signals. 
The bus priority objective Is of major importance since the 
bus service cannot fulfill Its function unless bus delays are 
kept to a minimum level. Furthermore, reduction of bus delays 
increases the reliability and the level of service of this 
mass transportation mode, making buses more attractive to new 
riders. It is evident that bus priorities at oversaturated 
intersections are even more essential for a successful bus 
service since the delays at such intersections are substan- 
tially higher. 

Clearly, if public transport vehicles are to be given 
priority at intersections, it must be accepted that this will 
be accomplished at the expense of the other users of the ■ 
intersection. That Is, the delays to the private vehicles 
will in genera]., increase when bus priorities are introduced. 
In recent rears, however, the Dhilosoohy in traffic managenienc 



79 



80 



has changed and the flow of people is considered to be more 
important than the flow of vehicles. Thus, when bus priori- 
ties are to be considered, minimization -of the total passenger 
delays rather than the total vehicle delays is the objective 
of the control. 

Due to the fact that bus volumes are normally fairly low, 
it is generally true that most acceptable bus priority strate- 
gies must provide bus priorities on a real-time basis; that 
is, the expected time of the bus arrivals at the intersection 
cannot be assumed to be known a priori , and priorities should 
be given only upon bus detection. In addition, since the 
intersection is over saturated and long queues are building 
up during the control period, an exclusive bus lane will be 
assumed at the bus approach. The bus lane -will not only sub- 
stantially reduce the bus delays by allowing the bus to bypass 
the queues, but it will also help to predict the expected 
time of arrival of a bus at the intersection with reasonable 
accuracy. In the analysis it will be assumed that the bus 
demand during the peak period is known and that the buses 
arrive from the approach associated with the highest satura- 
tion flow (if the buses arrive from the other approach, 
similar analysis applies) . 

With this preliminary Information a control strategy to 
enhance the bus priority objective will be developed. 



81 



5.2. Development of the Co ntrol Strategy 

According to the optimal control policy, during the 
first interval of the control period [0, x] the green phase 
is maximum on the bus approach; hence, further extension of 
the green interval to provide bus priorities will simply 
violate the minimum green phase constraint on the cross street 
Therefore, extensions of the main street green phase during 
this interval are precluded. It is possible, however, to 
shift the main street red phase to the right or to the left 
so that upon bus arrival the signal indication is green. This 
can be accomplished without violating .the minimum green con- 
straints,. The situation is illustrated in Figure 5.1, in 
which an""" indicates a bus arrival. When the bus arrives 
on green no action will be taken by the controller. The new 
policy provides the same amount oE green time within two 
cycles on both the main and cross streets and thus the slopes 
of the cumulative output curves are not affected. 

During the second interval [x, t, ] the red phase is 
maximum on the main street; however, it is not possible to 
shift this phase either to the right or to the left because 
such control action will violate the minimum green time con- 
straint placed on. the first approach. Figure 5.2 may be used 
to clarify this point. An alternative would be to shift the 
main street green phase to the right or to the left upon bus 
arrival, as is done with the red phase in the first interval. 
This control policy, however, '.-.'ill increase the red phase on 



82 



MinR-s+f—- Max G 



B^MI 




-formal cycle 



Main 
street 



p<%> Cross 



street 




Main 
street 



Shifting to the left 



IIP 



* ^%] 



■* Min6*J* MinR"*) 



I1ISL 



Main 
street 



^mx^m^m 






[? 



Cross 
WL. street 



Shifting to the right 



Figure 5 . 1 



33 



m Max R _^ 

s 


_ MinG^ 












m®m®m 


XV/yy\ 


Vy'yVv 


77^? 




^m^m^ 


















I * 




I Normal cycle 



Main 
street 



cross 
street 



Main 



S^S8&8£ street 






MinG 






Extended cycle 



Figure 5 . 2 



Cross 
street 



the first approach (i.e., the approach which is supposed to 
receive priority) beyond the maximum limit and such a policy 
is not acceptable since high red phases will disrupt the 
main street traffic. Another possibility of providing bus 
priorities during this interval is to extend the green phase 
(which is minimum) when a bus happens to arrive within a 
specified maximum range Z after the end of the green period. 
Since this policy does not violate any phase length constraint 
it will be adopted here. The policy is illustrated, in Figure 
5.2 where an " :: -" Indicates a bus arrival. 



84 

In summary, during the interval [0, t] the new control 
strategy will provide maximum green time on the bus approach 
and, if a bus arrives on red, the red phase will be shifted 
to the right or to the left. During the interval [t, t, ] 
minimum green time will be given on the bus approach and 
extensions will be granted to the buses that arrive within Z 
seconds after the end of the green phase. 

In the analysis it will be assumed that the switchover 
time and the final time remain unchanged. In order for this 
assumption to hold true it will further be assumed that the 
bus volumes are low so that the number of cycles disrupted 
by the buses is relatively small. The objective is to select 
the optimum value of the maximum extension interval Z that 
maximizes the total passenger savings resulting from the 
new policy. 

The analysis proceeds as follows. Let y represent the 
number of cycles during the time Interval [x, t-, ] and x the 
number of buses; the assumption of low bus volumes was meant ■ 
to imply that x is much smaller than y, i.e., x << y. Thus, 
the probability of a bus arrival at any cycle is 

■• P a - f < 1 _ ■ ■ ■ (5.2.1) 

where 

. t - x 
y = ~~ (5.2.2) 

Assuming that a bus can arrive with equal probability 
anywhere within the cycle (i.e.. the bus arrivals within the 



86 



d = sin D 



s in A 



A - 90 + 8 ? ■+ sin A = cos 2 



tan 9, 



Si g - j + s g^ : 

l°i!iin 2 & max 



D - o 1 - e ? 



tan 6 



S Cr ' + S cr I 

1^1 2^2 



1 



(5.2.9) 
(5.2.10) 

(5.2.11) 
(5.2.12) 

(5.2.13) 



where gl , g\ are given by Eqs . 5.2.6 and 5.2.7, respectively 
From Figure 5.3 it is also seen that 



a = (t-, -t) /cos6. 



(5.2.14) 



Substituting Eqs. 5.2.14, 5.2.10 and 5.2.12 into Eq. 5.2.9 
the following is obtained: 



VQ 2 




d = sinCe, -8,3 



37 

i -i< cSie-. oose. = Ct r -T)(tane 1 -tane 2 ) 

^ [ 5 . Z . 1 5 J 



and from Eqs. 5.2.8 and 5.2.15 it follows that 



AD 



j t , ( t , - t ) ( t an . - 1 an 8 - ) 



(5.2.16) 



Equation 5.2.16 is further simplified by using Eqs. 5.2.11 
and 5.2.13 to obtain 



AD 



c = JT t 1 (t 1 -T)Cs 1 -s 2 ) p. z 2 = az 2 



(5.2.17) 



where 



a 



4c" 



9 1 ^ i "^JL^-j-s-j — 



1^1 VJ K "l J 2-' v 



(5.2.18) 



The maximum delay saved to a bus by extending the green 
phase in the interval [t, t. ] is equal to the maximum red 



(1) 



phase r": * Similarly, the minimum delay saving is r' 



CD 



.00 



max 



therefore, the average delay saving is r^i - Z/2 , and the 

ill cl-A. 

delay saved to all buses is given by 



AD 



B 



ECr Cl) 4) 

1 max 2 J 



Z rr (l) Z _ r max ' 



c ■ max 2 



c 



x_ 7 2 
2c 



(5.2.19) 

If E 1 and E ? represent the average automobile and bus 
occupancies respectively, then the total passenger savings 
are 

) 

E 9 - ( a Z ) E - 



S = AD,, - AD 
B c 



fxZ r (1) 
max 



X 7 2 

2 c - J 



1 



(E 



X 



2c 



i', , a 



E,x r^' 

2 max 



(5.2.20) 



Th a 



ie optimum extension is obtained whe 



n 



8 8 



dS : 

d^Z 

solving for Z 



r E x 



+ E, a 



n a. a i 

z + .J HL^A = o 

c 



(5,2.21) 



(1) 
E„x r 

2 max 



= Z 



E ? x + 2E- ca opt 

From Eq. 5.2.21 the following is obtained 



(5.2.22) 



d__y3 
dZ 2 



= S" 



E ? x 
j 2c- + V 



(5.2.2 3) 



However, a is always positive because x, E, , E„ are positive, 

S, is greater than s~ and t-, is greater than x. Therefore, S" 
I s 2 1° 

is always negative, indicating that Z (Eq . 5.2.22) maxi- 

' & ' ° opt 

mizes the total passenger savings S (Eq. 5.2.20). 

A few important: remarks about the bus priority policy 
are necessary at this point. 

1. The red phase during the first interval [0 , t] can 

be shifted to the right or to the left by at most gJr;. - g T -i 

niaA mm 

seconds so that the minimum green time constraint on the bus 
approach is never violated. 

2. The bus priority policy will increase the total 
green time of the first approach by T (Eq^ 5.2.26) in the 
interval [t. t J , and because the final time and the switch- 
over point are assumed constant the maximum green time in the 
interval [0,T ] will be slightly decreased by the amount 



5g 



TfE 



Tc 



(5.2 . 24) 



Thus the new value of the maximum green time will be 



89 

a '- J - n L ' - 6 a f" C 9 ? C "i 

to max °max & ^' A ' •'J 

This decrease, however, will be very small because of the 

low b us volumes . 

3. The value of the maximum extension cannot exceed an 

upper limit; this upper limit' fZ ) is equal to e - cAf-' • 

. . • aax ; L c max °min' 

extensions beyond this limit will violate the minimum green 
time constraint placed on the second approach. Thus, if the 
value of the maximum extension obtained from Eq. 5.2,22 is 
higher than Z , the value of Z should be used for the 

Hi 3.X U13.X 

optimum extension. 



CHAPTER 6 
SYSTEMS OF OVERSATURATED INTERSECTIONS 

6,1. F ormulation of the -Unconstrained Problem 

The problem of optimizing the operation of more than one 
overs at urate d intersection in succession is studied in this 
chapter. To simplify the analysis initially two overs aturated 
intersections, such as the ones in Figure 2.2, are considered. 
Extension of the theory for more than two intersections is 
straightforward and is presented in Chapter 7. 

Consider a system of two intersections serving the traf- 
fic streams 1, 2, 3, and 4 as shown in Figure 2.2. If it is 
assumed that (1) the tra\ r el time between the two intersections 
is zero, (2) no turning movements are involved, and (3) the 
queue ing storage between the two intersections is zero, the 
analysis is greatly simplified. However, since the two inter- 
sections are treated as one, this formulation does not reflect 
real-world conditions. To place the problem on a more real- 
istic basis, these assumptions must be removed. The general 
minimization problem can be formulated in a manner similar to 
the previous problems, 

P r o b 1 e m : ' M i n i m i z e t h e del ay f u n c t i o n 

D = / Cx 1 +x.+x 3 +x 4 )dt (6.1.1) 

o * 

9 



91 



subject to 



£ 



dx 
1 = dt 

dx 



1 



q 1 -u 1 



2 



L l, . S 2 



2 at l 2 2- c , s -, 1 



f, 



dx 3 

dt 

dx. 



q 3 -u 2 



x 



dt 



q, 



4 "4 



(1-^-3 



— u 

S 3 2 



with the boundary conditions 



x 1 (0) 



x 2 (0) 

x 3 (0) 
x,(0) 




'1 



x. 







x 



w 



x 2 ct 1 ) 



x 3 Ct 1 ) 



x 4 (t x ) 










arid the admissible control domain 



f 1 1 
s., e ■ /c 



S„g - ' /c 
2°min 



mm - 1 - l 6 max / 



u„ < s,gj; 3 i/c 

— 7 & t t1 " "- 



mm — 2 



'max 



- u 



= u, 



(1) 
max 

(2) 
"max 



(6.1.2) 
(6.1.3) 
(6.1.4) 
(6.1.5) 



(6.1.6) 
(6.1.7) 
(6.1.8) 
(6.1.9) 



(6. 1.10) 
(6.1.11) 



In the ab o ve f o rraul at i on , 

t., is the end of the overs at ur at ion period 
x. (t) = x- is the queue length on approach i, 1=1,2,3,4 
q.j (t) = q. is the input flow rate on approach i, 1 = 1,2,: 
s^ is the saturation flow on approach i, 1=1,2,3,4 



u , ( t ) 



u. 



[ S ., g, ( t) j /c . Is a control variable associ 



l s l 



ated with the first intersectio 



n 



u 2 ( t ) = u „ = [s,g 3 (t3]/c 2 i s a c on t r o I v a r i ab 1 e as s o c I a t e d 

w 1 1 h t h e s e c o n d intersec t i on 



92 



g. (t) = g. is the effective green time on approach i', 
1 x i = 1 , 2 , 3 , 4 

fil 

g„ - is the maximum green time on approach i, 1=1*2 ,3.4 
"max rt ' ' ' ' 

gj" . "l is the minimum green time on approach i, 1=1,2,3,4 

c. is the cycle length of intersection j, j = l,2 

L. is the total lost time of intersection j, j=l,2 . 

x. is the queue length at time zero on approach i, 1=1,2,5,4 

f 
x;, is the queue length on the third approach at the final 

time. 
The implicit assumption is made here that the cycles c, 
and c 2 are constant while the green times can take on any 
value between a maximum and a minimum. At the beginning of 
the control period the queues may have values other than zero, 
whereas at the end all queues have been dissolved. The demand 
on each approach is time varying; however, the demand on the 
third approach is a function of the output of the first inter- 
section. This function can be determined by taking into 
account the left turns, on the first approach, the right turns 
on the second approach, and the" travel time between the two 
intersections. Alternately stated, the input to the third 
approach is equal to a portion of the output of the first 
intersection after some time delay d-, . If a represents the 
percentage of through vehicles of the first approach and b 
the percentage of vehicles turning right on the second 
approach, then the demand on the third approach is given by 



93 



q 3 (t) 



= a 



1" " 



f s 2 [c 1 -g 1 Ct-d 1 )-L 1 ]] 



I 



'1 



a u 1 (t-d 1 ) + b 



L 



S 9 (l-—-j - 

c l 1 



r 



= a u, (t- d, ) + b 



I 



L l 
1 



'1 



u 1 (t 1 -d 1 ) 



a - b J]u. (t-d ) + bjs 2 Cl~)| 

S^J X J. ^ i, 1 - 1 



(6.1.12) 



Let 



and 



S 2 S 4 

s , 1 ' s - 2 

1 3 



L L ? 



(6.1.13) 



(6.1.14) 



then 6.1.12 can be rewritten as 



q 3 (t) = (a-b£ 1 )u 1 (t-d 1 ) 



bm. n 



(6.1.15) 



The time delay d, can be assumed to be equal to the travel 
time corresponding to the average speed between the two 
intersections. The average speed is either estimated from 
knowledge of local conditions or, preferably, measured using 
floating car techniques as suggested in References 26 and 2 7 
As in the previous problems, the artificial state vari- 
able x„ is introduced such that 
U 



ax, 



3t 



- VW X 4 



(6.1.16) 



with initial and final conditions 



Xq(0) = and x n( t i) 



ree to vary 



(6.1.17) 



94 



Considering Eqs . 6.1.13 through 6.1.17, the problem takes 
the following equivalent form. 

Problem: Minimize the delay function 



t 



1 



Mm D - f (x, +x + x,+x,)dt = x n (t,) - Ma; 

v 1 2 3 A J ^ 1 J 

o 



- -^ (t 1 3 



(6.1.18) 



s ub j e c t to 



dx 



f 







dt 
dx 



1 



f. 



1 dt 
dx ? 



dt 
dx, 



1 2 o 4 



^r u i 



<VV £ i u i 



3 dt 



^ 



dx 
: 4 = dtT 



(a-b&, ) U-, (t-d, ) +bm, -u ? (t) 



q , -m 9 +£ 7 u 



4 2 2 2 



with the boundary conditions 



x. (0) = xV and x- ft,) 
i v - i l ^ 1 



and the admissible control domain 



(j) 



< ' < u . < u ^ - 1 •* 
mm — j — max 



j = 1,2 



(6.1.19) 
(6.1.20) 
(6.1.21) 
(6.1.22) 
(6.1.2 3) 



i = 1,2,3,4 (6.1.24) 



(6.1.2S) 



The implicit assumption is made here that the parameters a, 
b , an d d 1 are c o n s t a n t . 

The Hamilton! an function for the above problem is 
de Fined as 



9 5 



H = I A.f. = A (x 1 + x 2 + x 3+ x 4 j + A^q^u^ 

1 — u 

+ \ (o^-m +1 u ) + ^[(a-bLju- (t-d 1 )+bm 1 -u 9 ] 



■ 2 ^t7 •"! -i"! 



+ A 4 [q 4 -m 2 +^ 2 u 2 ] 



r l v 1" 



1 2 



(6.1.26) 



The adjoint variables A n , A-,, A ? , A~, and A, are given by 



dA, 



3H 



dt 


3x Q 


dX, 


3H 


dt. 


3x 1 


dA 2 


3H 


dt 


3x 2 


dA_ 
3 


3H 


dt 


3x, 


dA 4 _ 


3H 



= 



" " x o 



dt 



3x 



(6,1.27) 
(6.1.28) 
(6.1,29) 
(6.1.30) 
(6.1. 31) 



The solutions to the above equations are 



k n = const 

-V +k i 

~V +k 2 
" k t+k 3 
- k t+k 4 



(6.1.32) 
(6.1.33) 
(6.1.34) 
(6.1.35) 
(6.1.36) 



where 



.,., , k-, , k , k^, and k, are the integration constants 

U 1 L O 4 



Since x n ft 



0'- 1 



t-. ) is free to vary, it to Hows that 



dV 



\ ft ') ^ l± _ = V 

o l 'i J 8x o rt i J ° 



(6.1. 37) 



Hen a 



96 



A :[ (t) = 


■ t + kl 


x 2 (t) - 


- t -:- k 2 


A 3 (t) = 


- t + k 3 



A„(t) = t + k 



Sub sti tut.Ing the A ' s Into 6.1.26, 



(6.1.38) 

(6.1.39) 
(6.1.40) 
(6.1.41) 



H- -l(x 1 +x 2 +x 3 +x 4 ) + (t+k 1 )Cq 1 -u 1 ) + (t+k 2 )Cq 2 -m 1 +Jl 1 u 1 ) 

+ Ct+k 3 )[Ca-bA 1 )u 1 Ct-d 1 )+bm 1 -u 2 ] + (t+kj [q 4 -m 2 + £ 2 u 2 ] 

- [-t-k 1 +£ ] (t+k 2 )]u 1 + [(t+k 3 )(a-b£ 1 )]u 1 (t-d 1 ) 

+ [-t-k 3 +£ 2 (t+k 4 )]u 2 - (x 1 +x 2 +x 3 +x 4 ) + (t+k 1 )q 1 



(t+k 2 ) (q 2 -k ] _) + (t+k 3 )bm 1 + (t+k 4 ) (q^n^) 



= z 



Ll l + C^+k 3 ) (a-bi 1 )u 1 (t-d 1 ) 



Z-U- + w 



where 



*1 

7 

^2 
w = 



-t-Wt + k 2 ) 

-t-k 3 +£ 2 (t+k 4 ) 

-(x 1+ x 2+ x 3+ x 4 ) + Ct+1 
(t+k 4 ) (q 4 -m 2 ) 



l Jq l 



(6.1.42) 

(6.1.4 3) 
(6.1.44) 

(6.1.45) 



This is not a trivial control problem since the control vari- 
able u, appears in the equations of the process both without 
delay and with delay d, , The solution proceeds by introducing 
the shifted Hamiltonian function H, , defined as 



97 

H- l - I-I(t) + H.Ct+d,) 

= z 1 (t)u 1 (t) + Ct+k 3 )Ca-bA 1 )u 1 (t-d 1 ) + z 2 (t)u ? (t) 

+ w(t) + z 1 (t+d 1 )u 1 (t+d 1 ) + (t+d 1 +k 3 )Ca-bi 1 )u 1 Ct) 

+ z 2 (t + d 1 )u 2 (t+d 1 ) + w<t+d 1 ) (6.1.46) 

The maximum principle with nontrivial time delays of the con- 
trol is discussed in Reference 28, where the necessary con- 
ditions tor optimality are also derived. Application of the 
maximum principle to the previous time-delayed system yields 
the following necessary conditions. 

Theorem : For the optimality of the controls u, and u 
and their trajectories, it is necessary that there exists a 

T 

nonzero vector function A (t) = U (t), X,(t), \~ (t) , A,.(t) , 
A^Ct)], satisfying Eqs . 6.1,2 7 through 6.1.31. Furthermore, 
X (t) is such that 

dx 3H . . , 

(6.1.47) 

(6,1.48) 

(6.1.49) 

ar 1 = 9x7 • (6-1.50) 

dx 

W = 3AJ . (6.1.51) 

In addition, the following conditions must be satisfied: 



dt 


3A Q 


dx 2 


3H 


dt 


3 X 


dx 2 


3H 


dt 


3X 2 


dx, 


3U 

on 



98 

1. H(t,u* u|) = Max H(t,u,,u 2 ) ,1*1*1 

ff 1 Ct,u|,u*) = Max ^(t.LUj ,u 2 ) t-d 1 <t<_t 1 -d 1 (t>d 1 ) 
i.e., the optimal control must maximize the Hamiltonian and 
the shifted Hamiltonian at each time point in the above 
intervals . 

2. H(t 1? uJ,u*) = 

Condition 2 states that the Hamiltonian function at the final 
time must be zero. To satisfy the first condition as stated 
above, it Is necessary to examine the signs of 3H/3u and 
3FL/3U as In section 4.1. Thus, differentiating 6.1.42 with 
respect to U-, , the following is obtained: 



3TT7 = z l (6.1.52) 

and since z, is a linear function of time, there is at most 
one time point at which 9H/3u, becomes zero. Plotting the 
function H versus u, , the following results are obtained (see 
Figures 4.2, 4.3, and 4.4): 

1. If |IL - 2 > o * u * - u (1) 

3u, 1 1 max 

2. If ~- = z. < -> u* = u^ and 

3u, 1 - 1 mm 

l 

3. at •*— - = switch from u^ ' to u^.r . 

3^2 max mm 

Similarly, differentiating 6.1.42 with respect to u ? , it can 
be easily verified that 

3 H f?"\ 

3u 2 2 max 



99 

2. ir ?r — ■ = z n < ■* uS = u - and 

3u ? 2 2 mm 

- 3H n e ,4* t, r (2) + (2) 

3. at ~ = u switch from u^ J to u v . . 

3u 9 max mm 

Likewise, in order to maximize H, the following control must 
be applied: 

1. If *— = z 1 + (t+d + k„) (a-b£j = z^ > 

a U-| 1 _L o 1 

1 max 

if v-^ - z o > o ■+ u* = u UJ . 

3u ? 2 2 max 

3u, — 1 mm 

3R 1 m 

If «-=- = .z, < -»- u* = u lzJ . 
du„ 2 — 2 mm 

3H 1 fV] n 1 fil 

.5. At — - = z ( - ±J = switch from u UJ to u L1 -\ 
3u, max mm 

3H 

i c?i r ?N i 

At ^ = z - switch from u v " J to u v " J . 

3u- 2 max mm 

It should be noticed that in the common interval [d, , t-,-d, ] 
both H and H, must be maximized with respect to u, and u ? . 
Also, since z ? is a linear function of time, there will be at 
most one time point at which u„ is switched. It is therefore 
concluded that when no constraints are imposed, the optimal 
control policies of u, and u ? exhibit at most one switch each 
n o t n e c e s s a r i 1 y a t the s a me t i me point, 

In the previous analysis, no specific assumptions have 
been made concerning the demand curves Q_ , Q ? , Q_, and Q, . 
Assuming linear demand curves, a closed form solution can be 



100 



found for the switchover times and the final time t,-. This 
solution, however, is of little value since linear demand 
curves are unrealistic. Furthermore, the control policy 
allows negative queues and it is necessary to develop the 
theory to remove this defect. 

6.2. Optimal Control with S tate Variable Constraints 

The problem of constraining the queues is discussed in 
this section. Clearly, the theory developed in section 4.2 
is applicable to the queues x-, , x« , and x. since the state 
equations for these queues are not affected by the time delay 
d, . However, x 7 is affected by the time delay and it is of 
interest to examine the case where upper and lower bounds are 
placed on this queue. If cu and zero are the upper and lower 
bounds, respectively, it is required that 



a. 



(6.2.1) 



and 



x, > 



(6.2.2) 



When the above constraints are strict inequalities (i.e. , if 

x^ < a„ or X, > 0) for the entire control interval [0, t, 1 , 
3 3' 3 1 

the control variables u, and vu are not affected. One only 

needs to ask how the control is affected when the constraints 

( 1 ) f 2 ) 
are at equality for a finite time interval [t, ' , ti J "\ , 
1 3 ' 3 ■ ' 

i.e., what happens when 



(6.2.3" 



101 



or 



Let 



and 



x. 



= X. 



a. = 







(6.2.4) 



(6.2.5) 



(6.2.6) 



Without loss of generality, consider the constraint 6.2.1, 
Since Eq. 6.2.5 holds as an identity for a finite period of 
time, i.e., it is true independently of the value of t in 



the interval [t 



(1) A2) 



} , it can be differentiated with 



respect to time to obtain 



dx. 



di 



dt 



I . o 



(6.2.7) 



or, using Eq. 6.1.22, 



(a-b&i )u, (t-d, ) + bm. 



u 9 (t) = 



hence , 

u,(t) 



(a-b^ 1 )u 1 (t-d,) + bm 1 



(6.2. 8) 



(6.2.9) 



Therefore, when x, is at the upper bound for a finite period 
of time, the control action at the second intersection at 
time t is a function of the control action taken at the first 
intersection at time t-d,. In the special case where a = 1 



and 



1 



, Eq. 6.2,9 yields 



u 2 (t) = u 1 (t-d 1 ) 



(6.2.10) 



Equation 6.2.10 indicates that when no turning movements ar< 



io; 



involved, the control action at intersection 2 is the same 
as the control action taken at intersection 1, d, time units 
earlier. 

The adjoint variable X,(t) in the interval [ti , ti ' ] 
is derived from Eqs. 6.2.9 and 6.2.5. Let 



R. 



(a-b£ ] )u, (t-d, ) + bm, = iu (t) = 



t^<t<t!; 2j (6.2.11) 



at time w J it is required that 



V', 15 > - « 3 Ct(«) 



(6.2.12) 



:hus . X_ is given by 



dA 
dt" 



- f!£s 

J-0 1^5 



3 u. 



i 3u„ ' 



3R 1 



dX. 



(6.2.15) 



Substituting R, from Eq. 6.2.11 and the f.'s from the state 
equations 6.1.19 through 6.1.25 into Eq. 6.2,15, one finally 
obtains 



dA 



dt 



- 



t<»<t<t«) 



(6.2.14) 



Equation 6.2.14 shows that A~ is constant in the time inter- 



„ i r*.Cl) ,.(2)1 c „, 

val [ti , ti -i, Furthermon 



the following condition 



(1) 

, at time tr -' , X, must satisfy 

JO 



3S. 



- Tj-i - x-(t£ 

3 3x, 3 3 



(1) 



p , (6.2.15) 



Therefore, the constant value of X- during the interval 
r,(l) ,(2) 






J is obtained from Eq. 6.2.15. Proceeding as in 



103 



section -1.5, it can be .easily seen that 



,-(D . t (2) 



< 



(6.2.16) 



Since R~ must be zero in the interval [t^ 



(1) .(2) 



ti J ] , Eq. 6.2.9 



should be used to compute u ? , whereas u, is computed from the 
signs of 3H, /9U-, and 3H/3u, . From Eq. 6.2.9 it is also seen 
that 



s,g t (t) s ? s g , (t-d-,) L 

___£_; = ( a -b ~j -i-i i- + bs ? (l---) 



(6.2.17) 



Thus, g-(t) is computed from the above relationship. If the 
cycles c, , c and the saturation flows s 1? s , are equal, it 

follows that 



(t) = (a-b i l)g 1 (t-d 1 ) + b ^ (c 1 -L 1 ) 



(6.2.18) 



and in the special case where turning movements are pro- 
hibited , 



3 (t) - gl (t- dl ) 



(6.2.19) 



i.e., the green time at the third approach is equal to the 
green time at the first approach d 1 units of time earlier. 
When constraint 6.2.2 is imposed, Eqs . 6.2.6 and 6.2.7 yield 



dSL dS. 



dt 



dx , 

dt 



(6.2.20) 



Therefore, the same equations apply for the computation of 
the control variables u and the adjoint variable \~. 



104 

The problem becomes more complex when two or more con- 
straints are imposed. For example, suppose that constraints 
are placed on the queues x ? and x* such that 

x ? < a ? (6.2.21) 

and 

X- < <*- (6.2.22) 

When constraint 6.2.21 is at equality, u, must satisfy Eq. 

4.2.33, i.e., 

L s 

U l = [s 2 tl "'c^ :) " q 2 ] s~ (m 1 -q 2 )£ 1 (6.2.23) 

Similarly, when constraint 6,2.22 is at equality, u,. is com- 
puted from Eq. 6.2.9. Equations 6.2.2 3 and 6.2.9 form a 
system of two equations with two unknowns which have the 
solutions 

U l = (in l" q 2' £ l (6.2.24) 

u 2 - (a-b£ x ) [m 1 -q 2 (t-d 1 )3A 1 + bn^ (6.2.25) 

Therefore, when both constraints are at equality simultane- 
ously, u. and u ? are uniquely determined from Eqs . 6.2.2 3 
and 6.2.24. If, however, more than two constraints are 
imposed and they are at equality simultaneously, the problem 
is impossible since it involves the solution of a system of 
more than two equations with only two unknowns (the two con- 
trol variables). To circumvent this difficulty, it will be 
necessary to let the cycles c, or c, or both (depending on 
the number of constraints) free to vary between a maximum 



10! 



and a minimum value. If the resulting cycles lie outside 
their specified bounds the constraints will be violated. 

6.3. Solution to the Unconstrained Problem 

For the solution of the general minimization uroblem 
with time.- varying demands, turning movements, and time delays 
of the control, it is necessary to turn to numerical tech- 
niques. If minimization of the total system delay is the 
only objective of the control, the following algorithm is 
applicab le . 

STEP 1. Assume values for k, , k ? , k,, and k A . 

Since the integration constants k-, , k ? , k-, and k* (Eqs . 
& . 1 . 32 through 6.1.36) that are necessary for the computation 
of the adjoint variables are unknown, initial values must be 
assumed. The optimal solution is found by iterating on k, , 
k .-, , k,. an d k , . 

STEP 2. Set t fl} = 0, x^t^) = 0, x^t^ ) = x° , 

The time is set equal to zero (beginning of the control 
period) and initial conditions are the ones prescribed for 
t h e s p e c i fie p r o fa 1 e m . 

J. £ 

STEP 3. Put i = i + 1, t^ 1 ' = t^+At and 



X 



A 



ft 



CDi - t Ci) +lc 

J — X. r A. ■ 



106 



>(i), Ai)^ 



A -^ (^ L "" J — X ■ iv.-j 



4 

This step perforins numerical integration of the adjoint vari 
ab les (Eqs . 6,1.27 through 6.1.31). 

STEP 4, Find the values of z's at t*- 1 -', i.e., 

z (1} - Z 1 + (a-bA 1 ) [t (l ^ + d 1 +k 3 ] - 8H 1 /3u 1 

z x = -t ( '^ - k 2 + ^[t^+k,] - 3H/3u 1 

z 2 = -t^ - k 3 + £ 2 [t^+k 4 ] = 3H 1 /3u 2 = 3H/3u. 

The values of z's are used to determine the optimal policy. 

STEP 5, Examine the signs of the z's and determine the 

optimal controls u* and u*. 

If z^ > and z, > ■* u* = u' ll \ 

1 1 max 

If z^ < and z, < -* u* = u^ . 
— 1 — 1 mm 

If Z^ = z 1 ■- - T X - t (i) . 

If z = >0 ■*■ uS =* u v J . 

2 2 max 

If z < ■> u* - u^ . 
2 — 2 mm 

If Z, = + T 2 - t (1) . 

The optimal controls u? and u£ must 'maximize the Hamiltonian 
and the shifted Hamiltonian at each time point in the common 
interval [d, , t,-d, ]. If m 1 - 1 lies outside of this interval 



the optimal value of u, is determined only from the sign of 



F 7 



'1 



STEP 6. Determine the current state of the system. 

^it {l h - H {t il - l h - [ qi rt^^-u lC t^b]At i 



107 

x 2 (t (l) ) = x 2 Ct (i " 1} ) + [q 2 _Ct Ci) )-m 1 +£ 1 u 1 (t i )]At 

>w(t (l) ) = x 3 (t (l-1) ) + [(a-b£ 1 )u 1 Ct-d 1 3 

+ bnu-u, C"t ) ]At 
x 4 (t (i ^ - x 4 Ct (i - 1} ) + [q 4 (t (i} }-Hi 2 + 2 u 2 (t Ci} )]At 
x Q (t (l) ) = x (t (i " 1J ) + [x 1 (t (i) ) + x 2 Ct Ci) ) 

+x 3 Ct Ci) ) + x 4 Ct (:i) )}At, 
If x i < 1=1,2,3,4 set x. = and follow 

Steps 2a, 3a, 5a, and 6a of the constrained 
algorithm. 

This step performs numerical integration of the state equa- 
tions 6.1.19 through 6.1.20. 

STEP 7. Examine the value of H. 

Is H - z 1 u 1 +(t ( - 1 - ) +k 3 )u 1 (t^ 1 ^-d 1 ) + z 2 u 2 +w = 0? 

If "yes" put t 1 = t*- 1 -', D= x Q and go to Step 8. 
If "no' : return to Step 3. 

Since at the final time H is zero, the process must continue 
until H becomes zero. The total delay accumulated to this 
time point and the final time are the optimal if the remain- 
ing conditions are satisfied. 



Chech the state of the system at t, . 

Is the final state reached? 

If "yes," i.e., if x^t-,) = 1=1,2,5,4 ■* END. 

If "no" assume new values for x. 1=1,2,3,4 

X 



n n. cl re t u m t o Step 



10 8 

In this step the state of the system at the final time is 
checked to determine whether or not the optimal solution has 
been found. If the final state is the desired one, the 
assumed values for k, , k~ , k,, k. are correct and the itera- 
tive process is terminated. Otherwise, new values must be 
assumed by using an optimization routine which will minimize 
the objective function 

I - x^tp 2 + x 2 (t 1 ) 2 + x 3 (t 1 ) 2 + x 4 ( tl ) 2 

Therefore, Step 8 Is performed by the optimization routine. 

The obtained solution is the optimal because when the 
algorithm terminates, all the necessary conditions have been 
satisfied. Namely, (1) the Hamilton! an functions have been 
maximized with respect to time at each time point (Step 5) , 
(2) H is zero at the final time (Step 7) , and (3) the initial 
and final conditions are the specified ones (Steps 2 and 8). 

6.4. Sol ution to the Constrained Problem 

If constraints are imposed on the queues, the preceding 
algorithm applies only when the queues remain below their 
specified bounds. When the bounds are reached, It is neces- 
sary to follow additional steps that will be developed in 
this section. Without loss of generality, it will be assumed 
that constraints are placed on queue x, which is affected by 
the time delay d, , i.e. , 

I x i £ <** (6.1.10 



109 



To satisfy this constraint the algorithm changes as follows 



STEP 1. Assume values for k , , k~ , k~, and k,. 

STEP 2. Set t Cl} = 0, x Q (t Ci) ) = 0, x 1 (t (i) ) « xj , 

x. It J - X-,, X-^T J - \_ and x,(t v ) = x. 

Steps 1 and 2 are similar to Steps 1 and 2 of the uncon- 
strained algorithm. 



STEP 2a. Check the length of queue x,, 



If x 3 (t l " LJ ) > a 3 or x„(t Uj ) <_ 

put u*(t^) - (a-b£ 1 )uj(t (;i ^-d 1 )+bm 1 



If, however, u*(t^) < u ^ or u*ft^l > u ^ 
' 2 - mm 2 " -> max 

the problem is impossible. 

If x 3 (t^) > a 3 or x 3 (t^) < 

put x ~(t^) = a or X-Ct^J - and go to Step 3a. 

When the limits tend to be exceeded, the control u$ is com- 
pute d from Eq . 6.2.9. 

STEP 3. Put i = i+1, t (i) - t (i) -At and 
X Q = -1 

M't (i) ) = t^ +kl 

x 2 (t (l) ) = t Ci) +k 2 

x,(t Ci) ) = t^+k. 

A 4 ct j - t 'k 4 

Co to Steo 4. 



This step is similar to Step 3 of the unconstrained algorithm 



110 



STEP 5a „ 



Put i = i+ 1 , 
A (t Cl) ) - -1 

x 1 (t Ci:) ) = t (i) +k 



t'^ + At and 



-k. 



A 4 Ct (l) ) = t (i) + k 4 . 
Go to Step 5a. 



In this step the adjoint variable X, is kept constant; the 
step is bypassed if the constraints are not at equality. 



STEP 4 



Find the values of z's at t 



(i) 



l . e 



z^ = z, + (a-b*,)[t^ + d,+k T 3 = 3H./3U, 

J- 1 13 11 



-t^ = k x + ^ [t Cl ^+k 9 ] 



Z 2 = "* 



(i.) 



- k 



1 
£„[■ 



■2 



3K/3u 1 



Ci)*v 



k 4 ] = 3H 1 /3u 2 = 311/ 3 u. 



STEP 5. Examine the signs of the z's and determine the 
optimal controls u* and u* 

1 L 

If z^ > and z 1 > ■* u* = u^ . 

1 1 max 



If z 



^ < and z, < -»■ u* = u^ . 
1 — 1 mm 



f 7 (lj _ 7 _n_ >T _ t (lj 
I Z Z][ U T 1 Z 



If Z, 



-> u* = up\ 

2 max 



If 


Z 2 


< 





-> 


u 2 


= 


mm 


If 


•7 

~2 


= 





-> 


T 2 


= 


t<« 



Go to Step 6. 



Steps 4 and 5 arc the same as in the unconstrained algorithm. 



Ill 

STEP 5a. If z^ > and z, > -* u*- = u^K 

1 1 max 

If z^ Vj < and z., < -> u* = u^\ 
— 1 — 1 ram 

u* has been determined in Step 2a. 

This step is bypassed if the constraints are not at equality. 
According to the results of section 6.2, uS is a function of 
u* at time t-cL and is not determined from the sign of z ? 
but rather from Eq. 6.2.9. 



STEP 6. Determine the current state of the system. 

x 1 (t (l) ) = x 1 (t fl_1) ) + [q 1 Ct tl} )-u 1 (t tl ^)3At 
x 2 (t Ci) ) = x 2 Ct Ci ~ 13 ) + [q 2 Ct (i) )-m 1 +£ 1 u 1 Ct Ci) )]At 



X 3 



(t (i) ) = x 3 (t (i " i:) ) + [Ca-bJl 1 )u 1 Ct-d 1 ) 



-bm, -v.* C^ 3 ] At 



x 4 (t (i) ) - x 4 (t (i - 1} ) + [q 4 (t (i) )-m 2+ £ 2 u 2 (t (i) )]At 
x (t (i) ) - x^t^- 13 ) ♦ [x 1 Ct^ i) ) + x 2 (t^ i b 
4-x 3 (t (13 )+x 4 Ct (i) )3At. 

This step is similar to Step 6 of the unconstrained algorithm, 

STEP 6a. If x-(t^) < or x 3 (t^) > c* 3 

put A.(t W ) = Xjt^ 3 )*]!, and A 1 ^ = t^. 

This step is required to assure the discontinuity of A~ at 

time t' 1 '. 
5 

STEP 7, Examine the value of H. 

4 
[ s H = I X . f - » ? 

1 = x ;i 

If "yes" put t, = t '■ "■ , D = x Q and go to Step 8. 
If "no" return to Step 2a. 



112 



STEP 8. Check the state, of the system at t, . 
Is the final state reached? 

If "yes," i.e., if-x-Ct,) = 1 = 1,2,3,4 ■* END.. 
If "no" assume new values for x. i=l,2,3,4 
and return to Steu 2. 

Steps 7 and 8 are similar to Steps 7 and 8 of the uncon- 
strained algorithm, with the only difference being that In 
Step 7 the Hamiltonian function is computed from Eq. 6.1.26. 

The algorithm satisfies the conditions of section 6.2 
since (1] A remains constant during the period at which the 

constraints are at equality (Step 3a), (2) the jump condition 

'"1 ) 
at t^ - is met (Step 6a), and (3) the optimal controls u* and 

u* in the interval [tj , ti ] are determined according to 

the procedures developed in section 6,2. When constraints 

are imposed on the remaining queues, steps similar to 2a, 3a, 

5 a , an d 6 a m us t be f o 1 1 ow e d . 



CHAPTER 7 
EXTENSIONS OF THE THEORY 



7.1. Single Overs aturated Intersection 



Thus far, an intersection of two one-way streets was 
considered. However, the theory can be extended to an inter- 
section of two two-way streets where more than two approaches 
are overs aturated (assuming two-phase operation). For 
example, if the overs aturated approaches are four, the prob- 
lem is formulated as follows: 

Problem: Minimize the delay function 



D = / (x,+x 9 +x, + x,)dt (7.1.1) 

o 

S lib j C C t to 

dx 

ar" = f i = Q -r u C7.1.2) 

d X S 

- dl A - f 2 = V S 2 (1 -c 3 + s7 U C7.1.33 

dx, 

^ - f- = q,-u (7.1.4) 



dt 



■ j 



ith the boundary conditions 

x- (0) - x, (t,) - 1-1,2,3,4 (7.1.6; 



113 



x CO) - , x (t a ) 



free to vary 



114 



(7.1.7) 



u is an admissible control in the interval 

(1) 



s ^1) 
l^min 



c 



= u . < u < u 

mm — — max 



S <T 

2 "max 



(7.1.8) 



The solution proceeds as in section 4.1, I.e., by defining 
the Hamilton! an function 



4 
H = E 
i = 



(7.1.9) 



and setting 3H/3u = to find the optimal control. 

If the final time is fixed, i.e., If the end of the con- 
trol period is prescribed, it Is evident that the terminal 
control problem is considered, In this case, the Hamilton! an 
function at the final time is not zero and the algorithm of 
section 4.3 .is modified as follows. 



S T E PS 1 - 6 re m ain un ch an g e d . 
STEP 7. If t (l] 



t, go to Step 8, 



(i) 



If t l - J < t go to Step 3 



STEP 8. Examine the state of the system. 
Is x 1 (t 1 ) - and x 2 (t 1 ) - 0? 
If "yes" and H(t^) = H(t,3 END. 
If "no" or if H(t*- ^ ) f H(t,) assume new values 
for k, and k„ and return to Step 3, 



"I 



"2 



If the Initial conditions are different from zero, the only 
necessary modification would be to sot the values of the stat 
variables at time zero equal to the specified ones (Step 2). 



115 



7.2. Systems of Intersections 

The theory of Chapter 6 can be extended to a system of 
more than two consecutive overs aturated intersections on an 
arterial street such as the ones shown in Figure 7.1. To 
formulate the problem, the following definitions are necessary. 

M = the number of intersections. 



d. 



= -f-i^ 



the 



ime delay of intersection i (i = l ,2 , . . . ,M) , 
i.e., di is the average travel time between 
intersection i and the upstream intersection. 

j - the j approach to an intersection, j=l,2. 

q i j = the demand on approach i,j (i=l ,2 , . . . ,M; 3 = 1,2) 






i»j) f„(i,i) 



ls nax " ' ) - the minimum (maximum) green time on 



appro acn i f j 



s j_ -j - the saturation flow on approach i,j. 

U i = s l s i 7 ' c i = the cont rol variable at intersection i 

i-1,2,. . . ,M. 

c i = the cycle length at intersection i (i = l ,2 , . . . ,M) . 



L 



a- 



i , 1 



the total lost time at intersection i (i=l ,2 , . . . ,M) . 
= the percentage of through traffic on each hori- 



:ontal approach i,l (1=1,2 






2 - the percentage of vehicles turning right on each 



vertical approach i,2 (i=l ,2 , . . . ,M) 

the out 
5=1,2). 



°j a - tae output rate on approach i,j (i-1 ,2 ,. . . ,M; 



j7\ 



2 



I 
1 r\ 



n.M/ 



Fi euro 7 . 1 



116 

It is noted that q. . is a given function if approach 

i,j is an external approach such as all the vertical approaches 

and approach 1,1. If i,j is an internal approach such as all 

the remaining horizontal approaches, q. . is given by 

-*- > 3 

b-1 



'i,j (t) = a i-l,l u i-lO d P * b i-l,2 Si-l.Z^-HT., 

V 1-1 

i " 1 , 2 ,,. , J 

-s—rT^-l^Vj C7.2.1) 



Furthermore, the output rate o. -is 



u 



i if i,j is a horizontal approach (7.2.2) 

L. s . _ 

°i i = s -; ■ O--7— ) - - — '— u. If i j is' a vertical link 
,J ~' J i i,l X (7.2.5) 

The problem formulation Is: 

Problem: Minimize the delay function 



t 



1 M 2 



D = f * ,2 (x )dt (7.2.4) 

o 1=1 j=l ,J 



subject to 

dx. . 

f i,j = "^ = a i,J-°i,j i-1.2,...,M, (7.2.5) 

1 ■*■ ? « 

with the boundary conditions 

x i j CO 3 = X° i = l,2,... ,M; j-1,2 (7.2.6) 

x j iCtO - i=l-,2,... ,M; j=l,2 (7.2.7) 

and the admissible control domain 



S.V 1 ' 1 - 5 ,., ... s CT Ci,D 

J^iIL_ = u CO < Ll . < u d) = S l°max _ 

c. mm — 1 — max c. 
J - 1 



(7.2.8) 



117 



The solution proceeds as in Chapter 6, that is, by 

defining the Harailtonian function as 

2 
Z 

i»l j=l 

and the shifted Hamiltonians 



M 

H = I I A . . f . . 



(7.2.9) 



H i = H(t) + H(t+d 1 ) + 



H(t+d. .) i=2,3,.,.,M 

(7.2.10) 



The optimal control is obtained by setting dH/3u and 3fT. /3u 
equal to zero in the appropriate intervals. Constraints can 
also be imposed on the queues as in section 6.2. 



CHAPTER 8 
CONCLUSIONS AND RECOMMENDATIONS 

The preceding analyses of the optimal control of over- 
saturated intersections led to the following conclusions: 

1. For a single overs aturated intersection there 
exists at most one switch point if no con- 
straints are placed on the queues, 

2. When constraints are placed on the queues 
several switch points may exist. 

5. If one constraint is at equality the cycle 
length remains constant; however, the splits 
must be free to vary. 

4. If two constraints are at equality simul- 
taneously, the cycle length must be free to 
vary. 

■ 

5. In the special case where the demand is such 
that the intersection operates at capacity 
during the time interval In which the con- 
straints are at equality simultaneously, the 
cycle length is constant. 

6. The optimum cycle length is the maximum allow- 
able cycle length. 

7. Bus priorities can be granted without affect- 
ing the switch point, and the final time. 

S. For a system of two or more overs aturated 
intersections, there is at most one switch 
point per intersection, assuming that no 
constraints are placed on the queues. 

9, If constraints are placed on lengths of queues, 
conclusions similar to the ones of the single 
intersection are valid. 

10. For a system of two or more consecutive over- 
saturated intersections , explicit relationships 

1 1 S 



119 



between the control variables exist. That is, 
if d represents the average travel time between 
two intersections, the control action at the 
downstream intersection is a function of the 
control action taken at the upstream inter- 
section d time units earlier. 

Since the work performed in this dissertation is pri- 
marily theoretical, it presents some hypotheses that require 
further discussion. The major assumption is that the traffic 
voium.es during the peak period are predictable. However, the 
timing of pretimed signals is based on the implicit assumption 
that the traffic volumes have a repetitive and predictable 
pactern. Furthermore, case studies" ' have shown that the 
day-to-day variability in peak period demand is relatively 
small (approximately 1 percent). Nonetheless, if the day-to- 
day variability is statistically significant, it can be taken 
into account by using different timing plans according to the 
day of the week. Tt is also noted that accurate prediction 
of the demand is not crucial since the optimal control strateg; 
results in less total delay than the single setting strategy 
even if the actual volumes are substantially different than 
the predicted ones. This is illustrated by an example in 
Appendix A. The time variation of the demand during the same 
peak period is significant, but this has been taken into 
account by assuming nonlinear demand curves. 

In developing the theory, the implicit assumption was 
made that the saturation flow is constant during the control 
period. This, however, is an assumption common in most traf- 
fic signal control strategies and has been found to be Fairly 
real is ti c. 



120 

If real-time (feedback) control is to be considered, the 
optimal strategy will change frequently, based on information 
about the current state of the system and the predicted demand 
for the remaining control period. For this purpose, however, 
development of an adaptive prediction algorithm will be neces- 
sary. Some prediction algorithms have been proposed in Refer- 
ences 2 and 9. Nonetheless, these algorithms have not been 
used in practice, mainly because they oversimplify real -world 
conditions. Hence, further research in this area is needed. 
Improved traffic prediction models will also benefit existing 
real-time signal control schemes. 

Extension of the theory to multiphase signals is not 
simple and should be the subject of future research. The 
optimal control strategy for multiphase oversaturated signals 
will certainly become more complex due to the large number of 
control variables that are introduced. 

The problems considered in the previous chapters can 
also be studied with stochastic input. It should be pointed 
out, however, that stochastic optimal control is a new field 
in optimal control theory and, due to the complexity of the 
problems, complete mathematical analysis may not be feasible 
at tins time, 

Finally, the travel times (or time delays) between inter- 
sections were assumed constant. Although this assumption is 
practically realistic, the optimal signal control, problem 
with time- varying delays should be considered. At this time, 
however, optimal control with time- varying delays is a problem 



12: 



that "has not been solved theoretically and further research 
in this area is needed. 



APPENDIX A 
APPLICATIONS OF THE THEORY 

A . 1 . Introduction 

So far, the mathematics for achieving the optimal con- 
trol of overs at ur ate d intersections were developed (Chapters 
4-7). Using the results of the preceding theory one can find 
the optimal control policy for a particular situation. Then 
the optimal solution can be compared with sub-optimal policies 
which may require less control effort. Based on engineering 
considerations and judgment, a decision can be made as to 
whether or not. the optimal policy should be followed for the 
particular problem. As in most optimization problems, it is 
not necessary for the optimal solution to be always highly 
beneficial when it is compared with suboptimal solutions. 
It should be remembered that the optimal solution does not 
always imply bang-bang control; therefore switch points may 
not exist. 

For purposes of illustration of the theory, some typical 
examples are presented in the following sections. For each 
example a computer program utilizing the appropriate algo- 
rithms (Chapters 4-7) was developed. The algorithms incor- 
porate the use of an optimization routine. This routine is 
based on a searching method to determine the minimum of a 
function of N independent variables. 



123 

i 

In searching, one is interested in finding the set of 
values of the independent variables which yield the extremum 
(i.e., maximum or minimum) value for the dependent function. 
A set of values for the dependent variables is referred to as 
a location, and hence the general problem can be stated as 
finding the location at which the function takes on its 
e xt re mum value . 

Consider the case in which the initial location is given 
or selected at random, A new location is to be selected. 
There are two general qiiestions about the selection of the 
new location. One is the direction of the new location rela- 
tive to the old location, and the second is the distance 
between the locations. There are several searching strategies 
to resolve these two problems. In the sectioning procedure 
one moves in a direction which is parallel to one of the 
coordinates; one independent variable is changed at a time. 
In the steepest ascent technique one moves in the direction 
of the gradient of the function. In both of these techniques 
one can either move for an arbitrarily specified distance or 
one can move in the same direction as long as the value of the 
function is increasing (assuming that it is desired to maxi- 
mize the function). A new direction is then determined at 
the location of this local maximum. 

Symbolically, the general search problem can be stated 
as follows : 

Max: J - f(X (i + 1) ) - f (X^ + a (i) -p Ci) ) 



1 2 4 



subject to X v 7 as given 

p " as determined by a particular method 

where X^ ; = the i Lj location 

— (i) *.!. -th j. 

p v ■* = the i direction 

a = a scaler indicating distance moved. 
Once the direction has been chosen, the problem of locat- 
ing a distance at which a relative maximum occurs is the same 
problem as searching for the maximum of a function of one 
variable. In this case the variable is a^ . If one were 
able to choose the interval of interest and willing to make 

the assumption that the function was unimodal, then one could 

31 
use the Fibonacci search technique ' to solve the problem. Of 

course, there Is no need for determining the location of these 

restricted maxima very accurately since they may be a long way 

from the maximum value of the function. In fact, one is 

forced to make a choice between the time spent searching for 

the restricted maxima and the time spent in establishing a new 

direction, A search procedure can be described by stating how 

the direction vector p is determined. The search methods can 

be classified by whether they employ knowledge of the first 

and second derivatives in determining p". 



Th< 



re are several interesting points that could be men- 



tioned about the searching techniques and the interested 
reader is referred to References 31, 32, and 33 for more 
details, sln.ce detailed discussion on this subject is beyond 
the scope of this section. 



12 5 

The optimization routine incorporated in the computer 
programs is based on a searching method developed by Powell. 
Powell has shown that quadratic functions (such as the ones 
incorporated in the algorithms) result in faster convergence. 
According to this method, N direction vectors (p.) are set up 
for a function of N variables. On the first iteration they 
correspond to the coordinate directions. After N steps, a 
new direction X T -X„ is added to the set. Then p. is discarded 
and p. + , is stored in p. (i = l ,2 , . . . ,N) . Thus, the extrapola- 
tion direction is remembered and incorporated into the search. 
After N such iterations, all the original direction vectors 
have been replaced. Evaluation of the derivatives is not 
necessary and this is one of the reasons justifying the selec- 
tion of the subroutine. Reference 32 suggests that Powell's 
method is the most effective for cases where the objective 
function is a nonexplicit function of the independent vari- 
ables. The routine (called RMINSQ*) computes the values of N 
parameters that minimize the sum of squares of M functions. 

Input to the computer programs are typical traffic param- 
eters such as maximum and minimum allowable green intervals, 
saturation flows, cycle lengths, number of lanes for each 
approach, input volumes per lane in a tabular form, etc, The 
output of the programs are, in general, switch points (if any), 
final times, total delays, and all the necessary information 
that constitutes the optimal control policy. 



*RM1NSQ is a standard scientific subroutine available at 
the Northeast Regional Data Center of the State University 



Sys tern o t Florida 



A . 2 . ' The Unconstraine d Problem 

In this problem the objective of the control is to bring 
the state of the system to the origin in minimum time. Alter- 
nately stated, assuming that at time t = the queue lengths 
are zero on both approaches, one wishes to find the optimal 
control that ends the overs aturation period as soon as pos- 
sible and minimizes the aggregate delay. The queues are not 
allowed to become negative during the control period. 

Consider an intersection for which the following infor- 
mation is given for the two conflicting streams: 

Approach 1: Saturation flow: s, = 1400 v P hg = .388 veh/sec 

N unib e r of 1 an e s : 2 

Lost time: 1 = 3 sec/cycle 

Minimum green time: G> min -' = 50 seconds 

Input volumes (per lane): 5-minute counts as 

presented in Table A-l. 

Approach 2: Saturation flow: s = 1000 vphg - .2 78 veh/sec 

Numb e r of 1 ane s : 1 

Lost time: 1 ? = 3 sec/cycle 

Minimum green time: G) min ^ = 40 seconds 

Input volumes: 5-minute counts as presented in 

T ab 1 e A - 1 . 

The cycle length is assumed equal to 150 seconds and At equal 
to 2 seconds. 

The solution, is given by a computer program which utilizes 
the algorithm developed in section 4.2. The output of the pro- 
gram is shown In Table A-2. The first column of the table 



127 



Table A-l 



INPUT VOLUMES/LANE 

£ 5jc it ■=* ^ -* ^ A; ,t .TJC *r £ ^ 3X ;* £ ~ ^ ^c ^ £ ,*; *y ^ 

* APP«I * APP.2 * TIM" * 
drj£ * jjs * jSt •£:* iofc x A sn *ifc * % -jt jj! A414. A 5$: 



Q.» 


Q» 


0» 


121 • 


£6 O 


30 . 


2CS* 


147, 


5 » 


2 63a 




90 Oo 


3 i 8 * 


2 27 3 


1 2 * 


v 


257, 


15 3 0* 


3 96 a 


283, 


1300, 


430 9 


3C7„ 


2 1 » 


4fc2*, 


330* 


2400 3 


492* 


3=2, 


2 7 » 


523, 


373* 


3 » 


552* 


394, 


33 00, 


5 8 2, 


4-1 5 » 


3 600a 


6 i J , 


436. 


3 9 0, 


c4C» 


457* 


4200* 



indicates the iterations performed by the program. The 
second and third columns give the final time and the switch 
points which are obtained if k, and k~ (the integration con- 
stants of Eqs. 4.1.48 and 4.1.49) are specified as shown in 
columns 4 and 5. According to the algorithm, in every itera- 
tion the new values of k, and k ? are determined by the optimi- 
zation routine based on the value of the objective function 
which is shown in column 5. The objective function is equal 
to the sum of squares of the queue lengths at the final time. 
The last two columns give the value of the Hamiltonian func- 
tion H at the final time and the total delays, respectively. 
Finally, the optimum values of k-, and k ? that minimize the 
objective function are given by the optimization routine 
RMINSQ and arc shown below the table. Using these optimum 
values, one can go back to the table to find the optimal solu- 
tion. It must be pointed out that the optimal solution is 
not necessarily given in the last iteration since the 



12 8 



Table A- 2 



IT E P 


AT IONS 












tt ■& A -.v 


jjs x -^ sc ^c ■« 


% ^ -a; -wr ^c is 


& ^r jjs ^: $s i; ^ ?L' :.V :a; -x r? ak xc ^ -s -i; ^< 


ix $z ix ifi, ~>. $t ip -£ 


^e^;^ 4cfei< 


^:^k^t^:M^^c~jzi: 


* I 


* Tl 


* TAU 


* Kl * K2 * 


OBJ a * 


H * 


DELAY * 


* * A ^ 


**»*st 


£: jjc -J; i >c -i: 


te J: £ * ^( ;rc ;& 36 la A ^ -^ ^s « 3k ^ W ^ 


5^^ir.a;A :£ 3; 


_£. ^r *■ jjb $; $; 


^ -i )jc -fe li $ •< ^ A 


1 


1 426» 


902a 


—2569 a 78— 3236 »9 7 


96 a 3 


0, IS 


6 9,1 


2 


1 426, 


3SS, 


-2568»78-3235»9.7 


9 6,8 


0,05 


69,2 


J 


1 4 26 a 


904, 


-25 69» 78-3 235a 97 


96,8 


0,17 


69, 1 


4 


1424. 


8S8» 


-2572,27-3241 -,97 


96*9 


0, 16 


.69,1 


5 


14 2 8* 


9C4, 


-2567a 28-3231,97 


96»7 


0,14 


69,2 


6 


1432, 


912, 


-2562429-3221897 


96,5 


0,16 


69, 2 


7 


1 4 4 i 


9 2 8 • 


-2552,31-3201 a 9.7 


96,2 


0,19 


69 9 3 


8 


14 56s 


9 53 a 


-2532, 34-31 61 »97 


95* 5 


0, 11 


69,3 


9 


i 492 j 


1 013a 


- 24 92 . 4 1-3 3 1,9 7 


9 4,3 


0, 08 


70 ,3 


10 


1438* 


10 18a 


-2 49 So 79-3 86,97 


9 4a 5 


0, 02 


70 9 1 


11 


.1 4 9 6 * 


1018 , 


-2489«,03-3076,97 


94 9 


0, IS 


70,4 


12 


1 5 3 • 


1020 , 


-2432 , 23-3 56 ,9.7 


93,8 


6,73 


70,6 


13 


15 0s 


"iQ20« 


-2478a 64-30 61 a 97 


93*8 


6a 31 


70,6 


1 4 


1500a. 


10 20, 


-2471 « 37-3051 ,97 


93,6 


5, 46 


70,6 


1 5 


1500* 


10 13, 


-2456a 81-3031 »97 


93,7 


3,69 


70 »6 


16 


1500, 


I 016 9 


-2431» 34-2995,97 


93, 7 


0, 66 


70 ,6 


1 7 


1 546* 


1 014, 


-2402*2 4-2956*97 


90 a 3 ' 


0*01 


72 -, 7 


13 


1 5829 


1 012a 


-2344 e 03-2376,9.7 


79.» 8 


0, 10 


78 »4 


19 


1672 a 


10 10. 


-234 7a52-2681a97 


80,6 


0,01 


73, I 


2 C 


169 0s 


10 12* 


-2340» 53-2371 ,9.7 


79*2 


0,02 


78,7 


21 


1 71 0, 


1 C 12a 


-2333o53-2861,9.7 


77«> 6 


Oa 02 


79,5 


22 


1 752., 


1014, 


-2319,54-2341,97 


74,3 


0, 6 


31 3 


2 3 


1 £0 0, 


10 16, 


-2291 9 56-2801,97 


70 a 4 


0»69 


82 a 7 


24 


1854, 


10 16 , 


-2279), 25-2784,37 


65*7 


0, 03 


84*5 


25 


I 8 2 a 


1 23, 


-2234a 25-2786,95 


6 8a 9 


0., 3 


83 3 C 


2 6 


16 8 8 « 


1006, 


-2274, 25-2781,78 


6 2a 6 


Oa 04 


85 , 9 


2 7 


1 97 9 


9 3 2 3 


-2264* 2 5-2776 » 61 


5 5*2 


0,01 


89, 1 


p « 


2 23 8a 


9 38 s 


-224 4,2 5-27 6 6,28 


32 ,5 


a 5. 


9 7 , 1 


2 9 


15002* 


£ 5 , 


-2204,, 25-2745,60 


1 3 a 7 - 


1 1 a C 


1 07»9 


3 


2 72s 


960., 


-2 2 54, 18-27 71a 41 


46a 1 


0,01 


92 a 7 


3 1 


2 1 56, 


9 3 8 a 


-2247, 66-277.U 23 


38,9 


, 1 


95 a 6 


3? 


2 3 4 4s 


9 40. .» 


- 22 40 „ 84- 2 7 6 1 « 2 3 


22,4 


0, 00 


98,9 


3 "3 


2 700« 


940 „ 


-2234«C2~2 75ia28 


13,3 


2,23 


101,2 


3 4 


2656s 


940» 


-2236., 52-2754, 94 


1 4 .» 7 


0,0 


I 1 « 1 


3 5 


23 3 2* 


9 4 8 , 


-2241 a 52-2753*72 


2 3,1 


0, 


9 3, 4 


3 6 


2 7 0a 


93 2 « 


-2231 3 52-2 7 51 „1 6 


18,9 


la 89 


101,7 


37 


26 86»> 


9 3 8., 


-2235-, 53-2754,20 


17,2 


0, 01 


101,3 


3 3 


2622, 


9 4 2 , 


-2 2 37 a 7 2-27 55 a 8 5 


12, 1 


a 


100.9 


3 9 


2 613, 


942, 


-2238*01-2756,07 


11,9 


0,01 


100,9 


40 


26 26 • 


9 56 a 


-2238, 17-2751 ,07 


11,0 


0,01 


10 0, 1 


41 


2 644 s 


968 9 


-223853 4-2746*07 


11,3 


Gt»01 


99,4 


42 


2 6 3 4 * 


558, 


-2238a 21-2749,87 


11,4 


o, ci 


100,, 


4 3 


2624, 


952* 


-2238*13-2752*47 


11.3 


0,01 


100,3 


A '■+ 


2 £ 3 9 , 


5 t4 9 


-2 23 8* 17-2751 ,31 


1 1 a 6 


0*01 


100, 2 


45 


2 6 3 4s 


9 56a 


-2233, 19-2750*55 


1 1 a 6 


0,01 


100,1 


4-6 


2d93» 


974, 


-2240, 13-2746,07 


7,4 


0, 00 


93,9 


i? 


2 5 6 2 * 


994=, 


-2242 a 03-2741*07 


3,5 


0, 01 


97,8 


4 8 


2314a 


10 13a 


-22 44. a 4 3-2 7 35. s 6 


24, 1 


0, 00 


94,9 


4 9 


2 5 7 6 » 


986, 


-224 1 .,23-2 743,12 


4,9 


0,01 


96,2 


5 


2 5 6 2 o 


9 9 2 o 


-2 241 a 77-2741 ,36 


3, 7 


» 1 


9 7 ., 9 


5 1 


2 6 * 


9 74 a 


-2 2 39 a 98- 2 7 46 * 7 


7,5 


0,01 


9 9 , 9 


52 


2 32 6., 


1 1 4 , 


-2244, 1 9-2736, 07 


22,9 


a 


95,2 


b 3 


2 5 76s 


9 86 , 


-2241 „ 2 0-2743 8 I 7 


4 * 9 


0. 01 


9 3,2 


£ 4 


2572, 


9 9 a 


-2241 „ 72-2 741 ,9.4 


4 ,> 2 




98,0 


5 3 


si D U *$ 3. 


9 9 4 ^ 


-2241,, 98-2 741» 32 


3 4- 


0,00 


97,3 


$ --■ V -. 


>& £ v -ir ;i)S -£ 


^ i< 4; ~ *i -,? 


X :U ,)t ,-=c 5JC SjC ^fi .-^ & ^ J ,t A ^ rX £e .Jfi "*. & 


Se$ -A; jfc ->; i< Sjc jW if 


^ ^C -i- -;; £< 'a 


--. -.^ ^. _» m ^ ^i. _^ ^ 



LiPTIMAL SGUUTICN IS FOUNO,FO« 

■' t = - Z 2. 4 1 , 9 7 7 K 2 = - 2 7 4 1,318 



FIXED C DELAYS- 123 a 3 



optimization routine performs various tests to ensure as much 
as possible that the global minimum has been reached. 

From the computer printout (Table A-2, bottom) it is 
seen that the optimum values of k. and k. are -2 241.9 8 and 
-2741.32, respectively; from Table A-2 one can verify that 
these values are obtained after 55 iterations. On the 55th 
iteration it is observed that the switchover time is 994 
seconds and the final time 2558 seconds; thus the optimal 
control policy is to give maximum green time to the first 
approach (therefore minimum green time to the second approach) 
from the beginning of the oversaturation period until time 
T = 994 seconds; after this time minimum green should be 
given to the first approach and maximum to the second. The 
total delays that result from this strategy are 97.8 vehicle 
hours. However, one may choose not to follow the optimal 
policy and impose the single setting strategy. The single 
setting that ends the oversaturation period at time 2558 can 
be computed from the slopes of the output curves as follows: 

u l = slo ? e of output curve of approach 1 = constant 
a . to tal output i n time 2 55 8 4 7 7* 



2 55 8 2T58" 



0.1865 



and since 



3 l g l 



"1 c 

follows that 

*Froin Table A-l 



130 



(0.186 5) -150 
. 5 8 S 



72 seconds 



or 



G, = 72 sec + 3 sec ( = lost time) =' 75 sec = 0.50*c 

therefore, G ? = (l-O.SO)-c = 0.50-c. The total delay can be 

computed in a manner similar to the bang-bang control (i.e., 

the area between the input-output curves). The total delay- 
resulting from the single setting strategy is also shown 

below Table A-2 and is equal to 123.3 vehicle hours. Thus, 

the delay saved to the drivers is 123.3 - 97.8 = 25.3 vehicle 

hours. This means that the average delay per vehicle is 
reduced by the amount 



25. 



2(477) + 341 



71.0 second; 



It is therefore concluded that the bang-bang control is highly 
bene ficial . 



A. 3. The Optimal Cycle Length 

The problem of finding the optimal cycle length was dis- 
cussed in section 4.6, where it was concluded that the opti- 
mum cycle length is the maximum allowable cycle length, a pro^ 
ce dure already used in practice. 

In this section a numerical example is given to demon- 
strate this point. The input volumes, the saturation flows, 
and the remaining traffic parameters are the same as in the 
previous example. In addition, the upper and lower bounds 
■placed on the cycle lencth are assumed to be 100 and 1000 



131 

seconds , respectively. A cycle length o£ 1000 seconds is, 
of course, too high to be practical but is used here only for 
illustrative purposes. 

The total delay, the switchover time and the final time 
were computed for cycle lengths of 100, 200, . .., 1000 seconds 
and the results are illustrated in Figures A. 1 and A. 2 . The 
effect of the cycle length on the total delay is shown in 
Figure A.l. As can be seen from this figure, the total delay 
falls sharply when the cycle length is between 10 and 30 
seconds. For cycle lengths greater than 300 seconds, the 
delay savings are relatively small. 

Figure A. 2 shows the effect of cycle length on final time 
and switchover time. The dashed line in this figure shows the 
effect of cycle length on final time, whereas the solid line 
shows the effect on switchover time. Final time decreases 
with increasing cycle length, as expected. 

Cycle length also affects switchover time because of the 
change of the maximum output rates on each approach. That 
is, the maximum output rates (as defined in section 4.1) 
increase with increasing cycle length. In Chapter 4 it 'was 
shown that the switchover time is either the time x at which 
the z function (defined also in section 4.1) becomes zero or 
the time t^" J at which the maximum cumulative output curve 
of the first approach intersects the demand curve. If x is 
greater than t - - the switchover time is t^^ J , so that no 
negative queues are allowed. The intersection of these two 
switchover time functions produces the peak at c = 200 in 



is: 



no 



100 - 



(/) 



90 - 



S 80 



* 70 






60 

5 



2600- 



u 
o 
to 



6 

£ 2500 

rH 

aS 
■H 



2400 



100 200 300 400 500 600 700 800 900 1000 



Cycle (sec) 
Figure A.l 




10 2 00 



~ r~ 1 r~~ 

400 500 600 
Cy c 1 e ( sec" 

Figure A. 2 



900 



u 

soo e 



o 

-700.5 



600 y 

•H 



- 5 



00 



i 1 r r 

'00 800 900 1000 



135 

Figure A. 2. When c equals 100 seconds, x Is less than t ^ , 
i.e., the switchover point lies below the cumulative demand 
curve. When c is greater than or equal to 200 seconds, t is 
greater than t^^ J and the switchover point is the point of 
intersection of the input- output curves. 

A . 4 . T he Fixed Final Time Problem 

In this problem it is assumed that the final time is not 
free to vary but it is fixed. The objective of the control 
is to bring the state of the system as close as possible to 
the origin (zero state) at a given time t-, . Suppose that in 
the example of section 4.2 the final time t, is equal to 2100 
seconds. The question arises then as to how the control is 
affected by this objective. Alternately stated, it Is of 
interest to know if a switch point still exists, and If it is 
the same as in the free final time problem. The appropriate 
algorithm for the solution of this problem, as given in sec- 
tion 7.1, is incorporated in a computer program that generated 
the output of Table A- 3.. 

Inputs to the program are the same as in the previous 
example, the only difference being that t, is equal to 2100 
seconds. The output of the program is Interpreted in a simi- 
lar manner as before. It must be pointed out that since the 
final time is net free, the Hamilton! an function does not 
have to be zero. The optimal solution Is obtained in the 
14th iteration for k = -260 3.78 and k, - -3256.82. The new 
switchover time is 9 70 seconds and the total delays 



134 

Table A- 3 

T £ r. A T I C N S 

« I * Tl * TAU * Ki * K2 * QQJ* * H * DELAY * 

:*Ji«A*aa-ti*-Siis*x^3aiA*i?--i*a:^ ■$: * ,ft ■% 3? if if <8 -Jf * 4> ^ *• ** 5ft* 5K ♦ ♦ w ^ * * ^ * * ♦ ~ 

1 2100, 502* -2569»78-3236»97 44,33 49,17 S5<,8 

2 2100, 893» -2568.78-3236,97 44 a 42 49302 
2 2X00* 9C4, -2569* 78-3235*97 44,29 49,15 

4 2100, 333* -2572.25-3241,97 44„42 49* 57 

5 2'iGO, 9G4* -2567. 27-3231*97 44,29 43,72 
o 21C^ 9C6* -2365.2 2-3 229*39 44*25 4 8,56 
7 210 3* Si 4, -2 551 * 20- 32 19., 39 44*10 4-7,7 7 
a 2100* 924, -2553*74-32 35,0 2 43«94 46*53 
9 2100* 940=, -2543.70-3165902 43,75 44,94 

10 2100 3 938 4 -2539*51-3180.02 43,77 44*32 

13. 2100* 942, -2547^88-3 190*02 43,73 45=57 

12 2100, 946a -2556., 25-3200*02 435.70 46*82 

13 2100s 954-, ~2572 i 93-3220.,02 43,65 49,33 

14 2103=, 970* -2603*73-3256.32 43,61 53*99 

15 . 2100* 970a -2607,37-3261*32 43*61 54,54 
1c 2100., 970, -2614 3 56-3271 ,8 2 43*61 55*64 

17 2100* 970, -2623*93-3291,82 43*61 57,83 

18 2100* 972=, -2657*66-3331*32 43*61 62*29 

19 2100* 970, -2549»90-3181»82 43*61 45*74 

20 2100a 970* -2576, 84-3219*32 43,61 49,87 



■■* CPTIMAL SOLUTION IS FOUNCFCq 

Kl = -2603,73lK2=-3256«iS23 



95 * 


9 


95s 


7 


95 a 


9 


95* 


7 


95 » 


6 


95» 


~5 


94, 


9 


94, 


2 


94. 


3 


94, 


1 


94* 





93a 


7 


93, 





95 » 





93, 


Q 


93, 




93* 





93, 





93, 





accumulated until t-, = 210 seconds are 9 3,0 vehicle hours. 
Therefore, it is concluded that the switchover time with 
fixed final time is, in general, different than the switch- 
over time corresponding to the free final time problem. 

A. 5 . Th e Constrained Problem 

The optimal solution of section A. 2 minimizes the aggrs 
gate delay subject to lower bound constraints, but it does 
nor take into account the maximum queues that develop on the 
two approaches. In fact, if the demand curves have the 
general shape of Figure A. 3, the bang-bang control results 
in lower maximum queue length on approach 1 and higher on 



13S 



Q] 




n 




Figure A. 3 



approach 2 than the single setting control. This can be 
visualized by inspection of the figure. The output curve OAB 
results in lower queues on approach 1 than does the output 
curve OB, Conversely, on approach 2 the output curve OA'B' 
results in higher queues than does the output curve OB'. 
Thus, in general, it is the second approach that suffers if 
no constraints are placed on the queues. 



136 

Using the results of section A. 2, one can easily verify 
(by plotting the input-output curves or by numerical integra- 
tion) that the maximum queue length on approach 2 with single 
setting is approximately 80 vehicles. If the bang-bang con- 
trol is imposed the maximum queue on the same approach occurs 
at time x = 994 and it is equal to 

X 2 = Q 2 (t) - G ? (x) = 204 - {[(0.35)150-3] (0.278)/150) 
• 994 = 204 - 91 = 113 vehicles 

Hence, the maximum queue on this approach increases substan- 
tially with the bang-bang control, and it is desirable to 
impose constraints. 

In this example it is assumed that the second queue is 
constrained so that it does not exceed the limit of 80 
vehicles. The results (following the theory and. the algorithm 
of sections 4,2 and 4.4) are summarized in Table A. 4. The 
optimal solution is obtained on the 21st iteration for k., = 
-2361.48 and k ? = -2651.99. The optimal control strategy 
is as follows: 

1. From t = to t = 47 8 , u* = u 

' max 

2. At t = 4 78 (switch 1) the queue on the second 
approach is 80 vehicles and u* takes the value 
Of 0.191. 

3. At t = 15 2 (switch 2) the queue on the second 
approach is less than SO vehicles and at this 
time u" becomes maximum again. 

4. The average value of u* in the interval [478, 
1502] is .191. 

5. At t = 16 36;, u* is switched From maximum to 
minimum. 



137 



Table A- 4 



1 i c .-■ 

-j -a -J? -i 


-•, >■ A ji -fc i 


* * ■* * ■» ~ • 


* £ $ jje ^s * * ^ * *at * jt rx >■: A 5S« ."=; at A :js .)js * A * 


iri? ^^ ^: s« ^ 


:X ^^(^ixSi* 


* I 


» Tl 


* TAU 


# Kl * ., K2 - 


03J» * 


H * 


DELAY * 


» jit £ * 


Jj & :h. -if -^ rx 


i;ij*rii**^**?*^**)i:»?3*j* 


*;*,»:*--**:= 


it tt & 3- ;ar ^k la; 


ii?5c^-<Siic^:5c#c^; 


1 


1 680, 


16 2™ 


-24 74., 65-23 24 9 1 2 


80 « 5 


• 3 


83, 5 


2 


.16 30, 


1 602* 


-2474* 65-2324 £ ,l 2 


80*5 


0.03 


84,2 


3 


163 0» 


1602 9 


-24 74 «, 6 5-2324*1.2 


80,5 


0, 03 


84 a 2 


4 


1634, 


1558, 


-2473.65-2824.1 2 


80 „ 1 


* 1 


34,4 


£ 


1 5 3 a 


1604, 


-24 74, fc 5- 2 3 23,1 2 


80 9 6 


0,01 


84,2 


5 


I 6 3 o * 


1 6 C 6 a 


— 2 4 7 2 o 2 8— 2 3 I 5 » 1 2 


S ,> 1 


» 1 


84* 4 


7 


2 694* 


1610 9 


-2469. 92-2314 ,1 2 


79*6 


G a 10 


84. 7 


a 


1 706a 


1618* 


-2465s 20-23 04.-, 1 2 


73 • 9 


0, 04 


85 a 1 


9 


1722* 


1 6 23 » 


-2459,53-2792*1 1 


77 » 9 


0, 04 


85 a 7 


1 


17 50 9 


1645-, 


-2450a 09-2772^1 1 


76 »1 


0,0 3 


66 a 6 


1 i 


I 8 9 


16 80- 3 


-2431 •20-2732«l 1 


73, 2 


2s 2 2 


83,1 


12 


1 3 C • 


1 676 * 


-2426.90-2727*1 1 


7.3 »0 


Is 57 


83 a 1 


1 3 


laoos 


1674 a 


-2422=, 60-2722*1 1 


73,0 


0* 99 


88,1 


14 


13 0a 


1672* 


-2420.3 5 8- 2719. ,77 


72=9 


Os 63 


83, 1 


1 5 


1 822* 


16 68.5 


-2411 a 99-2709*77 


7 0,9 


0*02 


83. 9 3 


16 


19 4 0., 


1553* 


-2394, 79-2689 s 77 


60 « 3 


0, 02 


92 <> 3 


17 


2626 3 


1638, 


-2360,40-26 49 ., 7 7 


8»3 


0, 00 


10 0,9 


13 


2458a 


1634, 


-2362a 84-2654*77 


9.5 




100,3 


3. 9 


2700a 


1642 , 


-2357, 95-2644»77 


14» 7 


1,41 


100 a 3 


2 


2573, 


le35» 


-2361 * 31-2651 ,64 


5, ,3 


Q.00 


100 ,9 


2 1 


2 S 6 6 a 


16 36, 


-2361s 48- 2651 „ 99 


5»7 


0» 00 


1 » 9 


2 2 


2664 5 


1634, 


-2359 » 12-2649*59 


12,9 


0*00 


1 G 1 „ 


2 3 


23 94 a 


16 38, 


-23 63a 84-26 54*3 9 


13*2 


0,00 


100,3 


2 4 


2 5 fc3 6 , 


1 6 36 » 


~2361»04-265i»54 


6 » 




100 .9 


2 5 


2 5 7 2 , 


1 6 3 6 ■> 


- 2 3 6 1 , 3 5-2 5 51*35 


5,7 


v , j j 


1CQ»9 


!«ii a 


* -j 7 ';.• * A 


:'x :■: -^ *S fc ^ ' 


. ys £ x if, -,'", -v r, ; - -x. -x is .,< is- M "- -■;* it y. 


to -;< A A ;< sV >■ 


** **i» *■* 


if. it A -.-; lit A 4s $ * 



r OPTIMAL SOLUTION IS FOUND* FOR 

Kl ~~2 3 61* 481 K2=- 2651,93 



3 a ITCH I = 478, 
LCCNSTR. =0al91 



SWITCH 2 = 150 2., 



The trajectory of u is illustrated in Figure A, 4. The 
total delay with this control is 100,9 vehicle hours, which 
is still substantially less than the single setting control 
From this example it is seen that the control effort in- 
creases as the performance requirements increase, as expect* 





i 




' 




u 

u 




mar 










.191- 










mm 


' 









478 



ISO 2 16 36 
Figure A. 4 



2561 



A . 6 . Se n s itivity An aly s is 

The demand volumes are input parameters that are assumed 



to he known for a particular intersection. In 



the 



timing of pretimed signals is based on the implicit assumption 
that traffic volumes are repetitive and predictable. The pre- 
dictability of traffic is generally recognized as a fact, and 

29 30 
previous studies ' have shown that hourly volume variations 

for urban streets are fairly consistent. As an example, a 

report on the traffic, counting program in Cincinnati ' showed 

a variation of less than 1 percent during the peak periods 

-within a year. 

The total delay (objective function) changes if the 

demand volumes (input parameters ) are other than the predicted 

ones; however, the control action will remain the same when 

the signal operates on the pretimed node (open loop control). 

the one that corresponds. 



139 

to the estimated demand volumes. Based on actual counts, 
one can determine the daily variation of the demand volumes 
and study the effect on the total delays. Although the day- 
to-day variability is expected to be small, the variability 
within the peak period is significant;"" ' however, it has 
been taken into account by assuming nonlinear demand curves. 
This is indeed one of the advantages of the previously 
developed th e o r y . 

It will now be assumed that the volumes at the inter- 
section considered in section A. 2 can either increase or 
decrease by at most 10 percent. The total delay resulting 
from the two types of control (single or double setting) and 
the three volume conditions are calculated and summarized in 
Table A-5. The delay units are in vehicle hours. 

Table A-5 



^\Volumes 
St rat e gy^-v. 


-10% 


Predicted 


+ 10% 


Single 
setting 

Doub le 
setting 


74.1 
5 7.0 


12 3.3 

9 7.8 


19 3.1 

175.9 



From the tabic it is seen that when the volumes increase 
by 10 percent the total delay corresponding to the double 
sotting strategy increases by nearly 80 percent, whereas the 
delay with single setting increases only by 56 percent. The 



140 



double setting strategy, however, still results in lower total 
delay than does the single setting strategy. 

When the volumes decrease by 10 percent, the total delay 
corresponding to the double setting strategy decreases by 42 
percent while the decrease with the single setting strategy 
is 40 percent. Again, the double setting strategy results in 
less total de 1 ay . 

The results are illustrated in Figure A. 5 in which the 
total delay is plotted as a function of the volumes and the 
two control strategies. Clearly, the two curves do not cross 
over, Hence, it is concluded that the optimal control strat- 
egy results in less total delay than does the single setting 
strategy even in the case where the actual volumes are sub- 
stantially different than the estimated ones. This conclusion 
is important since it suggests that the developed theory is 
applicable in situations where accurate prediction of the 
demand is not possible. 

200- 






1S0-L 



(3* 10 






2 so- 




— — . Single setting 
Double setting 



10% 



+ 101 



Volumes 
Fi euro A. 5 



LIST OF REFERENCES 



1. D.C. Gazis and R.B. Potts, "The Overs aturated Intersec- 

t i oil , ' ' Proceedings of the Second International Symposium 
on the Theory of Road Traffic Flow , J. Almond, ed. , 
Paris: Organisation for Economic Co-operation and Devel- 
opment, 1965. 

2. A.J. Miller, "A Computer Control System for Traffic Net- 
works ," Proceedings of the S econd International Symposium 
on the Theory of Road T raffic Flow, J. Almond, ed. , 
Paris: Organisation for Economic Co-operation and Devel- 
opment, 1965. 

3. A.J. Miller, "Computers in the Analysis and Control of 
Traffic," Traffic Quarterly, Vol. 19, No. 4, 1965. 



D, Ross, R.. Sandys and T. Schlaeffi, "A Computer Control 
Scheme for Critical Intersection Control in an Urban 



N e tw o rk , " T r an s p o rtation Scienc e , Vo 1 . 5 , N o . 



19 7: 



D. Longley, "A Control Strategy for a Congested Computer 
Controlled Traffic Network," Transportation Research . 
Vol. 2, 1968, 

B. Lee, K. Crowley and L. Pignataro, "Better Utilization 
of Signals Under Oversaturated Flows," Highway Research 
Board, paoer presented at the mid-year meeting, Summer, 
19 74 (unpublished). 

D.H. Green, "Control of Oversaturated Intersections," 
Operations Research Quarterly , Vol. IS, No. 2, 196 8. 



. C! . Gazis, "Optimum Control of a System of Oversaturated 



Intersections , 



" n 



Derations Research, Vol. 12, No. 6 



1 Q 6 s 



M.I. Weinberg, H. Goldstein, T.J. McDade and R.H. Whalen, 
"Digital Computer Control System for Traffic Networks," 
NCHRP No. 29-, Highway Research Board, Washington, D.C, 
1966. 



10. D.C. Gazis, 
pp. 204-205 



raffle Science, New York: John Wiley, 1974, 



141 



142 



11. H. Kwakernaak , "On-line Optimization of Stochastic Con- 
trol Systems," Proceedings Third International Congress 
of International Federat i on of Automatic Control , London: 
Organisation for Economic Co-operation and Development, 
1966. 

12. L. Pignataro, K. Crowley and B. Lee, "Traffic Control 

in Oversaturated Street Networks ," NCHRP Project 3- (18) , 
Highway Research Board, Washington, D.C., 1974. 

13. P.G. Pak Poy, "The Use and the Limitation of the Poisson 
Distribution in Road Traffic," Proceedings Second Confer - 
ence of Australian Research Board, Australian Research 

Bo a rd , Sydney , KusTraTx3r^~T^62~r~ 

1 4 . A dvanced Control Technology in Urban Traffic Control 
Systems , Vol. 1, New York: Sperry Systems Management 
Division, 1965, 

15. R.L. Gordon, "A Technique for Control of Traffic at 
Critical Intersections," Transporta tion Science , Vol. 4, 
No. 3, 1969. 

16. L.S. Pontryagin , V.A. Boltyanski , R.V. GamkreLidze and 
E . F . M i s h ch e nk o , The Mathematical The or y of Opt imal 
Processes , New York: John Wiley, 1962. 

17. M. Athans and R.L. Falb , Opti mal Contr ol, Mew York: 
, McGraw-Hill, 1966. 

18. M.M. Denn, Optimization by Variational Methods , New York: 
McGraw-Hill, 1966. 

19. L.B. Coppel, Intro duction to Control T heory , Engelwood 
Cliffs, New Jersey: Prentice Hall, 1968. 

20. F.V. Webster, "Traffic Signal Settings ," Road Research 
Laboratory, Paper No. 39, Her Majesty's Stationery 
Office, London', England, 1958. 

21. J.M. Powell, "An Efficient Method for Finding the Mini- 
mum of a Function of Several Functions Without Calcu- 
lating the Derivatives," Compute r Journal, Vol. 7, No. 2, 
1964.' 



22. H.K. Evans and G.W. Skiles , "Improving Public Transit 
Through Bus .Preemption of Traffic Signals," Traffic 
Quarterly, Vol. 24, No. 4, London, England, 19 70. 

■.Junction Priority for Public Transport, 
,ab oratory, Report L.R. 5 70, London, 



R.A. 


Vincent , 


i*.o a ci 


Research 


Eng 1 s 


md, 19 7 3 



143 



24. "A Bus Priority System for Traffic Signals," Joint 
project between Kent State University Campus Bus Service, 
the' Center of Urban and Regional Studies, and the City 

of Kent, Ohio, prepared for UMTA (Project Ohio MTD-4) . 

25. H.S. Levinson, W.F. Hoey , D.B. Sanders and F.H. Wynn , 
"Bus Use of Highways: State of the Art," NCHRP Report 
143, Highway Research Board, Washington, D.C., 1973. 

26. D.T. Robertson, "TRANSYT: A Traffic Network Study Tool," 
Road Research Laboratory, Report L.R. 65, London, 
England, 1965. 

27. R.A. Vincent, "Traffic Survey Equipment for Measuring 
Journal Time," Road Research Laboratory, Report L.R. 65, 
London, England, 1965. 

28. A. Wierzbicki, "Maximum Principle for Processes with 
Non-trivial Delay of the Control," Automation and Remote 
Control , Vol. 10, 19 70. 

29. Highway Capacity Manual , Special Report 37, Highway 
Research Board, Washington, D.C., 1965. 

30. D.R. Howie and J.K. Young, "The Traffic Counting Program 
in Cincinnati," Proceedings Highway Research Board 1957, 
Highway Research Board, Washington, D.C., 1957. 

31. D.A. Pierre, Optimization Theory with Applications , 
New York: John Wiley, 1969. 

32. M. Auriel and D. Wilde, Optimization and Design , Engel- 
wood Cliffs, New Jersey: Prentice Hall, 19 73. 

33. D.J. Wilde and C.S. Beightler, Foundations of Optimiza - 
tion, Engelwood Cliffs, New Jersey: Prentice Hall, 1967. 



BIOGRAPHICAL SKETCH 

Panayotis George Michalopoulos was born on June 7, 194 8, 
in Nafpactos, Greece. He attended public schools in Greece 
and was graduated from El High School of Thessaloniki , Greece, 
in. June , 196 5 . 

In September, 1965, he enrolled at the Higher College of 
Engineering of Athens and received the Bachelor of Science 
degree in civil engineering in October, 1969. 

From October, 1969, to June, 19 70, he was employed as a 
highway engineer by A. Loukakos and Associates, a consulting 
firm in Athens, Greece. 

• He entered the Graduate School at the University of 
Florida in September, 1970, and was awarded a Graduate Research 
Assistantship in the Department of Civil Engineering. He 
received the Master of Science degree with a major in trans- 
portation engineering in March, 19 72. 

From March, 1972, to September, 1972, he was employed 
as a traffic engineer by the Florida Department of Transpor- 
tation in Fort Lauderdale, Florida. 

In September, 19 72, he enrolled in the Graduate School 
at the University o£ Florida and began work toward the Doctor 
of Philosophy degree wi th a major in transportation engineer- 
ing. He lias held a Graduate Assistantship with the Department 

of Civil Engineering. 

14 4 



I certify that I have read this study and that in my 
opinion it conforms to acceptable standards of scholarly 
presentation and is fully adequate, in scope and quality, 
as a dissertation for the degree of Doctor of Philosophy. 






A,? 



J ./ k:j Wat t lewo r th , Chairman 
Pipfessor of Civil Engineering 



I certify that I have read this study and that in ray 
opinion it conforms to acceptable standards of scholarly 
resent ation and is fully adequate, in scope and quality, 



P 



as a dissertation for the degree of Doctor of Philosophy. 



. , y y 
■y' yy 



K..--G. Courage 
Assistant Professor of 
Civil Engineering 



op: 



I ce ri 

.nion it 



fy that 1 have read this study and that in my 
:onforms to acceptable standards of scholarly 
presentation and is fully adequate, in scope and quality, 
as a dissertation for the degree of Doctor of Philosophy. 



£^£€^£ 



f* M& "- 



1H . S ch aub 
rofessor of Civil Engineering 









I ce r 


-j- 1 


fy th 





pi 


XI 


i on i t 


c 


on f o r 


p 


'fCs 


s 


entati 


on 


and 


a 


C 


cl 


di s s e 


rt 


ation 



at I have read this study and that in my 
ms to acceptable standards of scholarly 
is fully adequate, in scope and quality, 
for the degree of Doctor of Philosophy. 



t 

// y< 



//' 






/ 

i/ 



V. S: 



" D" 



Assistant Pr 
Civi 



5 s o r of 



certify that I have read this study and that in my 
it conforms to acceptable standards of scholarly 
■presentation and is fully adequate, in scope and quality, 
as a dissertation fo: 



the degree of Doctor of Philosophy. 



,/ 






<? 



R, ST T e avenwort h 
Professor of Industrial and 
Systems Engineering 



I certify that I have read this study and that in my 
opinion it conforms to acceptable standards of scholarly 
presentation and Is fully adequate, in scope and quality, 
as a dissertation for the degree of Doctor of Philosophy. 



// 



,/-"""" err, i 

(.,,/ ^vr^z v.^ L?'p J 1 & y. 

G. Stephanopoulos 

Assistant Professor of Chemical 

Engineering, University of 

Minnesota 



at ion w 

P P-r 



inis disse 

the College o 

w a s a c c e p t e d as p 

the degree of Doctor 



submitted to the Graduate faculty of 
and' to the Graduate Council, and 



artial fulfillment of the requirerac 
of Philosophy. 



nts 



ecember 



1 Q 7 C 





Dean , Colleges, of Engineering 



Dean , 



idu 



a.re 



School